SRM 647, D1, 500-Pointer (CtuRobots)

James S. Plank

Tue Aug 30 00:47:32 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2015
Competitors who opened the problem: 406
Competitors who submitted a solution:125
Number of correct solutions: 109
Accuracy (percentage correct vs those who opened): 26.8%
Accuracy (percentage correct vs those who submitted): 87.2%
Average Correct Time: 34 minutes, 32 seconds.

This problem was a little overwhelming live, as I had no clue how to solve it. But I simply bit off what I could, and then the solution evolved.

Let's ask ourselves a few questions:

Question 1: Given just two robots with capacities a and b that go in order, what's the maximum distance that the second robot will travel?
Clearly, the second robot will go half the distance of its fuel, plus half the distance of the fuel it gets from the first robot. To maximize the amount of fuel that it gives to the second robot, the first robot should travel a/3 units, give a/3 fuel to the second robot, and then travel back to the start. Think about why:
- If the first robot turns back before a/3 units, it can only donate fuel equal to the distance that it has traveled, because that's all the capacity that the second robot has. That amount will be less than a/3.
- If the first robot turns back after a/3 units, then it will have to donate less than a/3 units in order to have enough to get back to the start.
So, this means that the second robot will travel a maximum of b/2 + a/6 units.
Question 2: So, given two robots with capacities a and b, how should they be ordered? Let's compare -- when is:

a/2 + b/6 > b/2 + a/6?

It's a simple matter of algebra to show that it's when a > b. Good -- now we know how to order two robots. In fact, if you think about it, this means that if you have any number of robots, the one with the greatest capacity should go last.
Question 3: Now, given two robots with capacities a and b that are not the last robots, suppose robot b goes before robot a. How much fuel will they donate to the next robot? The equation here is going to be: a/3 + b/9. It's an easy matter to show that in order to maximize this quantity, a should be greater than b.
So now we know a very important fact -- given a collection of n robots, we should order them in ascending order of capacity to maximize their distance. Calculating the distance is a really easy O(n) operation.

So now that we know how to calculate the best distance given a collection of robots, we can turn our attention to choosing the robots. It seems quite natural to me to sort the robots in decreasing order of capacity. Then start to think of a systematic way to calculate distances:

Suppose we select the first robot to be in our set. It will be the last robot to go. Suppose its cost is c. Then the maximum distance will be determined by the maximum amount of fuel that the remaining robots can provide, subject to the constrain that their total cost is less than or equal to B - c.
Suppose we don't select the first robot to be in our set, but we do select the second. It will now be the last robot to go. Suppose its cost is c. Then the maximum distance will be determined by the maximum amount of fuel that the remaining robots can provide, subject to the constrain that their total cost is less than or equal to B - c.

This feels like a dynamic program. As always, the trick is setting up the recursion. Lets define the procedure MF(index,budget) to be the maximum amount of fuel that can be donated by robots whose indices in v are greater than or equal to index and whose total cost is less than or equal to budget. If we call MF(0,B), then that will be a third of the fuel that the last car got (including donations). You can multiply that amount by 1.5, and that's your answer (think about it -- you multiply by three to get the total amount of fuel, and since the last car is not donating any, you can go half that amount before having to turn back).

MF() will be a recursive procedure with the following cases:

Case 1: If index is equal to v.size() then the answer is zero.
Case 2: If budget is less than or equal to zero, then the answer is also zero.
Case 2: If you don't include robot v[index], then MF(index,budget) will be equal to MF(index+1,budget).
Case 3: Suppose the cost of robot v[index] is equal to c, and suppose that this cost is less than or equal to budget. Then you need to decide whether it's best not to include the robot (which is case 2), or to include the robot. If you do include the robot, then the amount of fuel that it donates will be 1/3 of its capacity plus 1/3 of MF(index+1,budget-c).

This gives you a recursive procedure to write, and of course you should see that it has to be memoized. The cache's maximum size will be v.size() * budget -- the constraints limit that to 5,000,000, so we're good to fit into topcoder's time limit.

Happy hacking!