TarifEzaz's blog

Wrong Answer on CodeForces 40 Div 2 Problem D
By TarifEzaz, 14 years ago, In English
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
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it
I just skimmed over your code, but my guess is that your path[][] array needs to also include k in it. From some state (i, j, k1) it may be possible to get to the end of the graph, but then it may also be possible from some state (i, j, k2) and your path array doesn't take this into consideration.

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).
→ Reply