Problem description
The basic idea of the problem was the following:
You are presented with a scenario where you have to travel a certain amount of miles in your car, and in the way there are a bunch of gas stations, each one of them with a different price. The idea is that you have to make your trip spending the least amount of cash, being careful not to run out of gas.
For the full description check: IEEE Extreme 2014
Input
- N (0 < N < 50001): The total number of gas stations.
- F (0 < F < 1000001): The units of fuel the car can take.
- T (0 <= T <= F): The units of fuel the car has at the beginning of the trip.
- L (0 < L < 1000000001): The path length of the landmarks he plans to visit
- Each of the following N lines will contain two integers: the first one, D_i (0 <= D_i <= L) corresponds to the distance of the station from the starting point, and the second one, C_i (1 <= C_i <= 1,000,000) represents the cost per fuel unit for that station.
Note: You may assume that the trip will be on a straight line
where all gas stations are spread on this line at the positions
specified by their D_i values
Basic concepts
- To try an get the best possible solution, the idea is to spend the least amount of money, making the necessary stops in they way, we don't mind the number of stops.
- We should not get extra gas than what we need to get to the end point (if we are left with extra gas, it means that we could've got less gas at the station and saved some cash)
- The trip may be impossible to do, as there may be a distance between gas stations that is greater than our fuel tank (in this case, even if we fill the whole tank we will ran out of gas in between stations).
- We should check if we have gas at the starting point
The solution
Well, the solution to this problem is pretty simple. It relies in only one idea, that is the following:
"If I need to get extra gas to perform the trip, I should always go to the cheapest station"
That is, if I can't do the trip without loading extra fuel, I should get it at the cheapest station. Even if it is not enough for the trip, I should aim at reaching to the cheapest station with zero gas, loading a full tank there and then continue with the trip.
Why get there with zero gas?
Basically, if I get there and have some fuel in my tank, I either got it from the start (it's ok) or load it somewhere else (not ok, because that means I could've got less gas earlier and load that amount here, that is cheaper)
Why should I load a full tank?
Well, if I can reach the goal with less fuel, then I should get the exact amount I need, but if that's not the case, I should get the whole tank, as anywhere else it will be more expensive.
So, what now? It's simple, just divide and conquer.
Let's imagine I only have to make one stop. I start with T units of gas in my car, get to the cheapest station load what I need there and continue to the goal, getting there with zero gas.
But, what if I need to make more stops? The problem doesn't change, you just have to solve it twice.
You choose the cheapest station (C).
START --------------------------- C ----------------------------------- END-GOAL
(1) (2)
(1) I start with T units of gas in my car and my goal is C. If I can't get there directly, I get the necessary amount of gas in the cheapest station to get to my goal with an empty tank.
* I load what I need (call it Y) at C.
(2) Then I start with Y units of gas at C, and my goal is the end goal.
If you can't get to C directly you will have the following scenario:
START ------------ C2 ------------- C ----------------------------- END-GOAL
(1) (2) (3)
where C2 is the cheapest station between START and C.
It is simple to see that you now have a recurrence problem. There's nothing else to say, just get a NASA trained monkey to code it.
No comments:
Post a Comment