(In the following article the thoughts can be taken as hints and can be used one by one for solving the problem. Directly looking at the entire solution is not advised)
Thoughts:
0. Always start with a solution that works. Be it brute force. While doing so, I would advice writing down an equation which represents the solution. Mathematical equation for required solution :
Min(i,q) = Min number of stops to reach end from position i when having q units of fuel.
Min(0,P) is the required answer.
Min(i,P) = 1 + min_(all j s.t d(i,j)<P) { Min(j,P+fuel(i)-d(i,j)) }
I am not giving away what i,j,P mean. Figure it out! Then proceed.
Now that you have figured out the meaning of equation. You can see that you have a solution already! It is a O(D*F) algo where D is the distance (start,end) and F is the max fuel.
1. Well i need to make sure that i dont run out of fuel which is exactly same as the distance i consume. So i am forced to pick atleast one spot before P units of distance from my starting point.
constraint: At any time in journey, i need to pick at least one of the spots within the road (current_postiion, current_position+fuel left)
(Principle: Always look at the constraints. Something you cannot avoid.)
2. Another line of thought to get to the answer is to keep on improving the answer. So lets say that i have a set of stops {S_i}. Can i make a better choice so as to reach my goal of minimum number of stops? Well let us look at the first stop s1. Can i make a better choice for s1? With the first thought, i know that i have to choose one of stops within P distance of starting point. So what is my best choice? Well the answer is Maximum Fuel Stop!! This also gives me hope that there is a possible greedy solution to the problem.
So i have to choose my first stop as max fuel stop in locaiton(0,P)
3. Now we generalise over 1. and 2. So this is how i am going to choose my stops
- max fue stop in (0,P) . let it be i
- available max fuel stop in (0, P + fuel(i)) say j
- available max fuel stop in (0, P +fuel (i) + fuel (j) )
- and so on.
4. choosing data structure for implementation.
i need a data structure that should be able to give me the max fuel locations. my queries are going to be of the form (0,i). i should be able to add new locations. The consecutive queries (0,i) (o,j) will be such that j>i. Also i need to delete the chosen location. Which happens to be the max fuel element in (0,i). So all these requirements point out to well known data structure.
Heap! In stl we can use priority queue. And we are done.
Thoughts:
0. Always start with a solution that works. Be it brute force. While doing so, I would advice writing down an equation which represents the solution. Mathematical equation for required solution :
Min(i,q) = Min number of stops to reach end from position i when having q units of fuel.
Min(0,P) is the required answer.
Min(i,P) = 1 + min_(all j s.t d(i,j)<P) { Min(j,P+fuel(i)-d(i,j)) }
I am not giving away what i,j,P mean. Figure it out! Then proceed.
Now that you have figured out the meaning of equation. You can see that you have a solution already! It is a O(D*F) algo where D is the distance (start,end) and F is the max fuel.
1. Well i need to make sure that i dont run out of fuel which is exactly same as the distance i consume. So i am forced to pick atleast one spot before P units of distance from my starting point.
constraint: At any time in journey, i need to pick at least one of the spots within the road (current_postiion, current_position+fuel left)
(Principle: Always look at the constraints. Something you cannot avoid.)
2. Another line of thought to get to the answer is to keep on improving the answer. So lets say that i have a set of stops {S_i}. Can i make a better choice so as to reach my goal of minimum number of stops? Well let us look at the first stop s1. Can i make a better choice for s1? With the first thought, i know that i have to choose one of stops within P distance of starting point. So what is my best choice? Well the answer is Maximum Fuel Stop!! This also gives me hope that there is a possible greedy solution to the problem.
So i have to choose my first stop as max fuel stop in locaiton(0,P)
3. Now we generalise over 1. and 2. So this is how i am going to choose my stops
- max fue stop in (0,P) . let it be i
- available max fuel stop in (0, P + fuel(i)) say j
- available max fuel stop in (0, P +fuel (i) + fuel (j) )
- and so on.
4. choosing data structure for implementation.
i need a data structure that should be able to give me the max fuel locations. my queries are going to be of the form (0,i). i should be able to add new locations. The consecutive queries (0,i) (o,j) will be such that j>i. Also i need to delete the chosen location. Which happens to be the max fuel element in (0,i). So all these requirements point out to well known data structure.
Heap! In stl we can use priority queue. And we are done.
thank you
ReplyDelete