INOI 2010 Twin Robots

general
, ,
1

Hi people,
During the current INOI practice contest, i saw that INOI 2010 question 2 has been asked. Can someone help me formulate a Dp solution for it. I don’t wish to cheat, rather I wish to learn how to solve a graph + DP type problem. The contest ends at 10:00 pm, and by then it’ll be too late to learn anything new, so I request help right now and also request others not to cheat during the 'practice ’ contest using any solutions below…

This is my current DP formulation, yet I believe the following recurrence relation might just go on and my base case(s) are incorrect. Yet, here goes:

sum(i, j, k, l) = grid[i][j] + grid[k][l] + max(sum(i-1, j, k, l-1),sum(i, j-1, k-1, l))
                                                  if(i > 0 & l > 0)      if(j > 0 & k > 0)

sum(0, 0, 0, n-1) = grid[0][0] + grid[0][n-1]

I tried implementing this DP, but there are loads of bugs and it does’nt yield any results… Help creating a better reccurence and/or in debugging my code will be appreciatted. thanks in advance…

2

Your DP equation is correct. You might be having some implementation bugs.

3

Hint: can you figure out k, l from i, j?

2 Likes
4

What idraumr said.

5

R2D2 (i, j) ====== C3PO (j, N - i - 1)

1 Like
6

Here’s a shortcut…
You rotate the matrix anti~clockwise 90° and you matrix add the accepted matrix and the rotated matrix. Now you have to find the max point path from TL Corner to BR corner…considering you can move down or right only.