H: Robot Challenge
We had wanted this problem to be a Dynamic Programming problem, and early versions of it had large input limits that would force DP. However, other constraints caused us to put limits on it, making it solvable by other means. It was in our “second wave” of problems. The “first wave” was Knitting and Minesweeper – every team that solved one or two problems solved one (or both) of those two. This problem and “Euclid” made up the second wave – every team that solved 3 or 4 solved both problems in the first wave, and then one or two from the second wave. Every team that solved more than 4 solved both problems in the first wave, and both problems in the second wave.
OK, here’s the Judge Input, the Judge Output, the main Solving Program, another java solution, one in C++, another in C++, and one using a different technique.
Look in the spoiler for not one, but two solution ideas!
[spoiler]
The original intent was for this problem to require Dynamic Programming. Create an array best[], where best[i] is the best you can do from here to the end if you stop at target point i. Clearly, best[i] can be computed pretty simply from best[i+1], best[i+2], and so on (best[i] = Minimum over k of [1+(the cost of skipping targets between i and i+k) + (the Euclidean distance between i and i+k) + best[i+k]]. ). So, start at the end, work back to the beginning, and best[0] is your answer.
The numbers were small enough, however, that a simple, best-first-search shortest path (aka Dijkstra’s Algorithm) would work. Define the “Distance” between two targets as 1 + (the Euclidean distance) + (the cost of skipping targets in between). Then, just run Dijkstra’s Algorithm and voila.
Note: in both cases, the “1+” is for the one second that the robot must stop on a target point.
[/spoiler]