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.

Hi,

I recently encountered a problem in my algorithms class. The problem is as follows:

"You are driving a bus along a highway, full of rowdy, hyper, thirsty students and a soda fountain machine. Each minute that a student is on your bus, that student drinks one ounce of soda. Your goal is to drop the students o quickly, so that the total amount of soda consumed by all students is as small as possible. You know how many students will get o of the bus at each exit. Your bus begins somewhere along the highway (probably not at either end) and moves at a constant speed. You must drive the bus along the highway; however, you may drive forward to one exit then backward to an exit in the opposite direction, switching as often as you like. (You can stop the bus, drop o students, and turn around instantaneously.) The bus travels at constant speed.

Describe an efficient algorithm to drop the students o so that they drink as little soda as possible. Input consists of bus route (a list of exits, together with travel time between successive exits), the number of students you will drop off at each exit, and the current location of your bus(which is also an exit)."

Initially, I was thinking of a greedy strategy to choose the exit at minimum distance from my current location (choose one with maximum drop-off capacity if more than one exits), and then continue from the new location. However, this does not result in optimal solution.

Can anyone give a hint for the expected DP solution over here ?

Thanks.