Codejam 2014 - Round 3 - Last Hit

2 Dec 2015

This one is pretty difficult. I cannot solve it. However, I've realised a bunch of clues that the solution must be DP.

First of all, let's make this clear. When Diana skips a turn, it means that she accumulates more shots that we can later use at her turn. This is not clear from the problem statement. It's surprising that a lot of people solved the problem correctly. WTF!

This problem looks like a greedy algorithm. When Diana has a chance to kill a monster, she should do so. However, this is not always true. There are certain cases where she should wait to get a bigger prize.

Another clue is that the boundaries of the parameters are awfully low. That's the clue. It's so low that you might be able to brute-force with recursion. In this case, you can brute force the large dataset with recursion + memorization, which is essentially a top-down DP.

Since Diana can save her shots for later use, there's no need for Diana to shoot any other monster than the closest one. That simplifies the problem. So, at her turn, she can choose to skip, shoot one shot, or shoot many shots. That's it. That's the recursion. And we get the maximum gold.