Hi guys. I'm getting Wrong Answer for Test 10 in Problem D of the CodeForces 40 Round. Here's my code http://ideone.com/be1hs
I used a Dynamic Programming approach to solve this problem. My states here are
1) the current row position of my pawn
2) the current column position of my pawn
3) the remainder of the sum of all the numbers that the pawn has covered so far.
Upon termination, my recursive function will store the biggest number ( divisible by k + 1 ) that can be achieved, coming to a particular position with that particular remainder.
Regards
tarif
I used a Dynamic Programming approach to solve this problem. My states here are
1) the current row position of my pawn
2) the current column position of my pawn
3) the remainder of the sum of all the numbers that the pawn has covered so far.
Upon termination, my recursive function will store the biggest number ( divisible by k + 1 ) that can be achieved, coming to a particular position with that particular remainder.
Regards
tarif
edit: By this I mean your 2nd state (i, j, k2) may overwrite path[][] and then if your final answer uses state (i, j, k1), it will print out the direction set by state (i, j, k2), not the direction set by state (i, j, k1).