You are not logged in. Please login at www.codechef.com to post your questions!

×

INOI 2010 Twin Robots

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

nibnalin's gravatar image

6★nibnalin
1611414
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) Organic-Shilling0★

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
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×1,750
×1,092
×353

question asked: 30 Jan '15, 20:01

question was seen: 1,406 times

last updated: 31 Jan '15, 19:28