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.
A naive solution would be to start a tour from each gas station in turn, and check if the tour is feasible. A feasible tour is one where the fuel in the tank never goes negative while travelling. This is an O(n^2) algorithm.
However, it is easy to see that if a tour starting from S1 and passing through S2, S3, ..., Sk is infeasible, so is a tour from any Sj between S1 and Sk. So you don't need to check those, and the algorithm becomes O(n).
I am not sure queues were needed either -- but that's a cute opportunity to learn from the editorial :)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Truck Tour
You are viewing a single comment's thread. Return to all comments →
This is one of the easiest hard problems maybe.
A naive solution would be to start a tour from each gas station in turn, and check if the tour is feasible. A feasible tour is one where the fuel in the tank never goes negative while travelling. This is an O(n^2) algorithm.
However, it is easy to see that if a tour starting from S1 and passing through S2, S3, ..., Sk is infeasible, so is a tour from any Sj between S1 and Sk. So you don't need to check those, and the algorithm becomes O(n).
I am not sure queues were needed either -- but that's a cute opportunity to learn from the editorial :)