We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I have had a hard time with similar problems before.
Simply put, there are 2^m possible paths to test. This is easy, unless they are too many. Which they are.
Dynamic programming helps, but not that far. Memory is not enough to remember paths (since they only occationally overlap) and/or there are too many solutions to calculate to do it in time.
It is (perhaps) possible to eliminate some subset of paths.
Can anyone give a hint?
Is dynamic programming with some twist possible?
Or a completely different approach required?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #208: Robot Walks
You are viewing a single comment's thread. Return to all comments →
I have had a hard time with similar problems before.
Simply put, there are 2^m possible paths to test. This is easy, unless they are too many. Which they are.
Dynamic programming helps, but not that far. Memory is not enough to remember paths (since they only occationally overlap) and/or there are too many solutions to calculate to do it in time.
It is (perhaps) possible to eliminate some subset of paths.
Can anyone give a hint? Is dynamic programming with some twist possible? Or a completely different approach required?