ZIO09002 - Editorial

PROBLEM LINK: ZIO 2009 Problem 2

Editorialist: Rohit Mazumder

PROBLEM:

In a N x N square grid, find the maximum sum path from any of the squares to the edge of the grid. In each turn, we can move to a square to the right, or to a square down.

EXPLANATION:

Let a(m, n) denote the value at the square (m, n) in the grid.

Let f(m, n) denote the maximum score we can obtain if we start at the square (m, n) in the grid till we cross a boundary of the grid.

So, the question essentially asks us to find max{f(m,n)} for 1<=m<=N, 1<=n<=N.

From a square if we move to the square on its right, then the maximum score we can get is = a(m,n) + f(m,n+1).

Similarly, on moving down, maximum score obtainable = a(m,n) + f(m+1,n)

Now, from a square on the grid we would love to move to a square which will enhance my score the most.

That is to say,

f(m, n) = max{ a(m, n)+f(m+1, n), a(m, n)+f(m, n+1)}

Or, f(m, n) = a(m, n) + max{ f(m+1, n), f(m, n+1)}

where,

f(m+1, n) denotes the maximum score we can obtain if we move the token to the bottom of the current square.

f(m, n+1) denotes the maximum score we can obtain if we move the token to the right of the current square.

a(m,n) denotes the value of the current square which is added to our score.

Base Cases and Edge Cases :

  1. If we start at the rightmost and bottom-most square, i.e, m = M and n = N, then the total score we can obtain is a(M,N) as there is no other square left to shift our token too.
    So, f(m,n) = a(m,n) ; for m = M and n = N

  2. If we start from a square situated on the right-most column, i.e, 1<=m<=M-1 and n = N,
    Then we can shift the token to the square below it, or end the game by moving the token outside the right boundary.
    So, f(m,n) = max{a(m,n), a(m,n)+f(m+1,n)}
    or, f(m,n) = a(m,n) + max{0, f(m+1,n)} ; for 1 <= m <= M-1 and n = N

  3. If we start from a square situated on the bottom-most row, i.e, m=M and 1<=n <= N-1,
    Then we can shift the token to the square to the right of it, or end the game by moving the token outside the lowermost boundary.
    So, f(m,n) = max{a(m,n), a(m,n)+f(m,n+1)}
    or, f(m,n) = a(m,n) + max{0, f(m,n+1)} ; for m = M and 1 <= n <= N-1

Combining all cases, the final recurrence for the problem,

f(m, n) = a(m, n) ; m=M, n=N

f(m, n) = a(m, n) + max{0, f(m+1, n)} ; for 1<=m<=M-1 and n = N

f(m, n) = a(m, n) + max{0, f(m, n+1)} ; for m=M and 1<=n <= N-1

f(m, n) = a(m, n) + max{f(m+1, n) + f(m, n+1)} ; otherwise

The answer to our problem is max{ f(m, n) ; 1<=m<=M, 1<=n<=N}

Solving the given example :

To solve, we solve the recurrence derived using a dp-table. We fill the table from bottom to top, as demonstrated below.

Step 1: We know that f(5,5) = a(5,5) = -9 (According to condition 1 of recurrence)

Step 2: Fill the rightmost column from bottom to top using condition 2 of recurrence

2
7
7
-3
-9

Step 3: Fill the bottom-most row from right to left using condition 3 of recurrence

2
7
7
-3
8 1 -2 4 -9

Step 4: Fill the rest of the cells starting from (M-1, N-1), row-wise from right to left , using condition 4 of recurrence.

10 11 4 12 2
11 1 10 1 7
15 10 2 1 7
5 12 8 1 -3
8 1 -2 4 -9

Step 5: Answer = Maximum value in the table = 15

Subtask 1:

23 14 13 12 8
25 13 16 1 12
13 29 6 13 6
23 16 20 -2 10
13 20 4 13 -16

Answer = 29

Subtask 2:

4 7 3 8 -2
8 3 9 3 5
2 9 4 8 -2
9 3 7 1 5
2 7 1 6 -4

Answer = 9

Subtask 3:

14 18 12 16 9
20 13 16 3 13
13 19 9 8 1
15 7 14 4 3
4 13 2 9 -2
8 -5 5 -4 5

Answer = 20

2 Likes

Actually, I am sorry to say but I am unable to undersand the solution. Can you please help me?

Thanks for the effort
:slight_smile:

Sure. Can you please specify the portion you are unable to comprehend?

Thanks for the quick reply. Actually, I don’t know about dp table. So FIrstly I will learn about that. If then too, I didn’t understand, I will surely ask you about my query.

(Please tell good resources to learn about DP table and DP in general, if you know any.)
Thank You Very Much for the contribution.

These two resources :

:slight_smile:

3 Likes

@mazumder7
@sudheerays123

Brother, I am in Class X. And I am getting No idea about the maths behind these solutions. Should I consider registering for ZIO this year or should I train myself for attending it next Year.
:slight_smile:

Thank You

Today is last date to register for ZIO …

2 Likes

I would say choose fast. Because today is last day for registration for zio

1 Like

@everyone
@sudheerays123
@leo_valdez
Actually, I got to know that the medium of examination is offline and the centre nearest to me is actually more than 400KM. And also, I have my PreBoard Examination on the same day. So I decided to skip this year and will train myself Harder for the next Year. I would be so grateful of you If you give some recommendations for where to begin from… Wish me Luck

Thank You
:slight_smile:

  1. Introduction to Competitive Programming
  2. Youtube playlist - Coding blocks
  3. Algorithms with problems
  4. Hackerearth Codemonk
  5. Introduction to programming contests - Stanford
  6. Data structures and algorithms- Codechef discuss
  7. Recommended reading
  8. Nice blog for beginners
  9. ICO preparatory material - CC
  10. Collection of CP resources - Google drive
  11. Commonlounge - Cp from beginner-expert

Some other useful links I found

4 Likes

Thanks, For the Efforts

@mazumder7 your dp table in subtask 3 has dimensions 5 × 6, whereas the input has dimensions 6 × 6. I also used the same method but got the answer greater than 20