SRM 647, D1, 500-Pointer (CtuRobots)

James S. Plank

Tue Aug 30 00:47:32 EDT 2016
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:

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:

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:

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!