http://codeforces.net/gym/101047/problem/F
I have been trying(unsuccessfully :-( ) to solve this problem for quite some time now. This is my attempt so far.
Initially, I sort the Rajasis in ascending order of their hit points, breaking ties with ones which give greater recovery points. Then, I am doing a bottom-up DP, with two states — position, no of spells remaining. dp[pos,sp] contains the minimum strength required to kill Rajasi at position "pos" using at most "sp" spells. Finally, if there is a valid configuration for pos=0, the answer is "Y", else "N". This approach gives WA on test #2.
Please help me figure out if my approach is wrong. Thanks for your help.
This approach doesn't work. You don't necessarily need to kill them in order of their health. For example H = 11, Rajasis = (10, 9), (9, 1). You should first kill the rajasi with greater health.
The solution is: First, use the greedy approach for all the Rajasis such that y_i >= x_i, that is, always kill the rajasi with greater y_i — x_i such that H > x_i. If there are some remaining Rajasis with y_i >= x_i that you can't kill, you have to use spells.
After that, for all the Rajasis such that y_i < x_i, you have to use DP kind of like you said, but you need to sort them in decreasing order of y_i. It can be shown by the swap method that this is an optimal order. That is, show that if you can kill (x_1, y_1), (x_2, y_2) in this order, and y_1 < y_2, then you can also kill them in the order (x_2, y_2), (x_1, y_1), remember to use that x_i > y_i.