SPAR3 - Editorial

ratik_21 · March 19, 2019, 9:36am

PROBLEM LINK:

Contest

Author: Ratik Jindal
Tester: Udit Gulati
Editorialist: Ratik Jindal

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

DP, Math.

PROBLEM:

Given a M\times N Grid with each cell having a value C[i][j], you have to reach (M,N) from (1,1) picking coins from current cell given that you can only move towards RIGHT , UP or DOWN from a given cell. Print the maximum value after reaching (M,N).

QUICK EXPLANATION:

We can use Dynamic Programming to solve this problem. Let Dp[x][y][dir] be the total maximum value we have after reaching (x,y) and coming from direction dir( which can be up , down or left).We have our recursive equations as follows -

If ( dir == UP ) : Dp[x][y][up] = grid[x][y] + max( Dp[x+1][y][up] , Dp[x][y+1] ).
If ( dir == DOWN ) : Dp[x][y][down] = grid[x][y] + max( Dp[x-1][y][down] , Dp[x][y+1] ).
If ( dir == LEFT ) : Dp[x][y] = grid[x][y] + max( Dp[x-1][y][down] , Dp[x][y+1], Dp[x+1][y][up] ).

We would just need to memoize our recursive equations to avoid repetitve calls and return the answer.

EXPLANATION:

Let us solve an easier version of this problem first.The problem is almost same except that now from each cell you can move towards RIGHT or DOWN only.

Now In such case , the number of states in our dp solution reduces to 2 i.e from a cell (x,y) you can go to (x+1,y) or (x,y+1). The basic Dynamic Programming solution is(starting from (M,N) and reaching (1,1)) :-

Dp[x][y] = grid[x][y] + max( Dp[x+1][y] , Dp[x][y+1] ).

Coming to our Original problem (which is just an extension of the above problem) , if we try to apply above startegy then our solution fails because :-

If Dp[x][y]= grid[x][y] + max( Dp[x+1][y] , Dp[x][y+1] , dp[x-1][y] ).
then dp[x+1][y] = grid[x][y] + max( Dp[x+2][y] , Dp[x][y+2] , dp[x][y] ).

So , Dp[x][y] calls Dp[x+1][y] and Dp[x+1][y] again calls Dp[x][y]. This will cause infinite calls and our solution won’t work. Therefore to overcome this , we need to add an extra state to our Original solution.

Let this state be dir : Direction from which you came to the cell (x,y).

So now , Let Dp[x][y][dir] be the total maximum value we have after reaching (x,y) and coming from direction dir( which can be up , down or left).We have our recursive equations as follows -

If ( dir == UP ) : Dp[x][y][up] = grid[x][y] + max( Dp[x+1][y][up] , Dp[x][y+1] ).

The above equation simply means if you’re coming to cell (x,y) from above , you can move towards Right or Down , just pick the maximum of these two.

And Similarly the other equations are :-

If ( dir == DOWN ) : Dp[x][y][down] = grid[x][y] + max( Dp[x-1][y][down] , Dp[x][y+1] ).
If ( dir == LEFT ) : Dp[x][y] = grid[x][y] + max( Dp[x-1][y][down] , Dp[x][y+1], Dp[x+1][y][up] ).

The value of dir can be assigned using numeric values ( 0 : UP , 1 : DOWN ,2 : LEFT).We would just need to memoize our recursive equations to avoid repetitve calls and return the answer.

COMPLEXITY:

O(M*N*3) time and auxiliary space.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.