×

INOI 2010 Twin Robots

 0 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... asked 30 Jan '15, 20:01 6★nibnalin 161●1●5●17 accept rate: 0% Your DP equation is correct. You might be having some implementation bugs. (30 Jan '15, 20:40) ketanhwr6★ 2 Hint: can you figure out k, l from i, j? (30 Jan '15, 21:09) idraumr0★ What idraumr said. (30 Jan '15, 21:13) superty3★ 1 R2D2 (i, j) ====== C3PO (j, N - i - 1) (30 Jan '15, 22:34) 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. (31 Jan '15, 19:28) arpanb83★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,214
×1,236
×399

question asked: 30 Jan '15, 20:01

question was seen: 1,527 times

last updated: 31 Jan '15, 19:28