TWOPATHS - Editorial

PROBLEM LINK:

Contest

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Dynamic programming, Greedy, Recurrence Relations(basic), Prefix Sums

PROBLEM:

You are given an N * M grid with an integer in every cell.
A path in this grid is defined as a sequence of N cells, starting from a cell in the bottom row (N-1, j)\,0 \le j < M, and for every cell (i, j) except the last cell in this path, the next cell is of the form (i - 1, j) or (i - 1, j - 1).

The number of moves of the form (i - 1, j - 1) should be \le K, where (i, j) is a cell in the sequence.

For any 2 paths, where the distance between their starting cells is \ge K + 1, Path-Sum is defined as the sum of the values between these paths, including the values on the 2 paths.

Your task is to determine the maximum possible Path-Sum

EXPLANATION:

Points to be noted:

  • 0-based indexing is used throughout the entire editorial.
  • The colours used in the diagram below donā€™t follow with the colours used in the question.
  • \text{INF} here refers to maximum possible value required under the constraints, ideally 2e9. This will work (as you will see further) as the sum of all values in the grid is at the most (or at the least) \pm1e9.

Let the 2 endpoints of the \text{Blue} region (bottom row) be p_1, p_2 respectively.
The leftmost blue cells in every row represent the cells on a path starting at p_1. The rightmost cells are defined similarly for a path starting at p_2.
Let these 2 paths be P_1, P_2 respectively.

Thus, the Path-Sum between P_1 and P_2 is the sum of values in the blue region.

Now, let us start with finding the best paths P_1 and P_2 (starting at p_1 and p_2 respectively), such that the Path-Sum between them is maximised.

The \text{Blue} region can be defined as (\text{Red + Blue}) - \text{Red} (colour notations as in the diagram above). Maximising the above equation suffices to maximise the Path-Sum.
How do we maximise the equation?

Maximising the first term (\text{Red + Blue}) while minimising the second term (\text{Red}) suffices to maximise the whole equation (Greedy logic).

Before we proceeded any further, think about what would happen if 2 paths intersected! Yes, our \text{(Red + Blue)} - \text{Red} equation would become invalid, as the two sets (\text{Red} and \text{Blue}) can no longer be independently computed (overlapping cells would result in double counting).
However, note the constraint on the distance between p_1, p_2 (|p_2 - p_1| \ge K + 1). How does this really help us? Notice that since the number of (i-1,j-1) moves are restricted to K, the 2 (valid) paths can never intersect! Trivial proof, left as an exercise.
(If this constraint was not present, the question would become even harder!)

Letā€™s first figure out on how to maximise \text{Red + Blue} region. Letā€™s call this \text{Red + Blue} region as the \text{Purple} region. A basic (incomplete) recursive solution would be as follows (Out-of-bound cases are not being handled in these snippets to keep them short and clean):

Maxim(i, j)            
	return Prefix[i][j] + max(Maxim(i - 1, j), Maxim(i - 1, j - 1)); 

\text{Prefix}[i][j] refers to the sum of the first j values in the i^{th} row and should be computed beforehand.

What does this code do? \text{Maxim}(i, j) tries to find a path starting at a (i, j) such that the sum of values enclosed between this path and the first column (the \text{Purple} region) is maximum possible. Lets examine the recurrence part by part:

  • \text{Prefix[i][j]} : Since we are finding the sum of \text{Purple} region with the pathā€™s start at (i, j), all the values between (i, 0) and (i, j) are included in this sum, thus the prefix sum is taken.
  • \text{max}(\dots) : Now we can either take (i - 1, j) or (i - 1, j - 1) as the next cell in our path, based on which helps in maximising the sum.
  • \text{Maxim}(i - 1, j) : This gives a recursive call to the same function to find the maximum possible sum in a cropped grid (cropped till the (i - 1)^{th} row) with starting cell (i - 1, j). This is defined similarly for \text{Maxim}(i-1,j-1).

Understanding on recurrence relations is required to fully understand the above part.

Wait. However, we have another constraint. This is on the number of (i-1,j-1) moves, so adding that into the recursive implementation yields:

Maxim(i, j, cnt){
	if(cnt < 0)
        return -INF;
 
	return Prefix[i][j] + max(Maxim(i - 1, j, cnt), Maxim(i - 1, j - 1, cnt - 1));
}

We have added an extra variable \text{cnt} that determines the maximum number of (i-1,j-1) moves that can be made after reaching this function call.

Note that exactly \text{cnt} moves of type (i-1,j-1) may not be required to achieve the maximum in the current recursive call, as we are only trying to maximise the overall sum, and not the number of (i-1,j-1) moves (while remaining within the valid range).

So, our recurrence only calculates the max possible sum using utmost (note the word utmost here) \text{cnt} \,\, (i-1,j-1) moves.

Note the \text{cnt}-1 on the recurrence call of \text{Maxim}(i-1,j-1), as one (i-1,j-1) move is being done in this case (so the number of (i-1,j-1) moves available/possible decreases by 1).

An extra parameter check has also been added to make sure \text{cnt} doesnā€™t go below 0 (as this is not possible). Why do we use -\text{INF} here? Because, the function call asks for the maximum possible, so returning -\text{INF} complies that this move is not possible.

The recursive call \text{Maxim}(N-1,j,K) is run for every value 0 \le j < M, as we are trying to find maximum of the \text{Purple} region for every cell in the bottom row as the starting cell, with maximum (i-1,j-1) moves restricted to K moves (constraint in the question).

Yes! We are effectively done with the recurrence. But can this be made better? Further observations leads us to the fact that multiple calls are made to the same values of (i,j,\text{cnt}) which shows existence of overlapping sub-problems. This calls for Dynamic Programming. From the above recurrence, its quite clear that the states of the DP are [N][M][K + 1] (corresponding to i,j and \text{cnt}) .

The final code with memoization added is as below:

Maxim(i, j, cnt){
	if(cnt < 0)
        return -INF;
	
    if(DP[i][j][cnt] == Computed) //Computed is an abv. of whether 
        return DP[i][j][cnt];	  //this state has been calculated  
    
	return DP[i][j][cnt] = Prefix[i][j] + max(Maxim(i - 1, j, cnt), Maxim(i - 1, j - 1, cnt - 1));
}

This code is now ready! Now we are coming back to computing the minimum of the \text{Red} region.

How do we do this? Simple! Change max to min and weā€™re done. Also, the prefix sum shouldnā€™t include (i,j) cell of the function call, as the values on the path are included in the \text{Blue} region(Path-Sum includes the values on the 2 paths too).

The modified code for finding the minimum of the \text{Red} region is as follows:

Minim(i, j, cnt){
	if(cnt < 0)
        return INF;

    if(DP1[i][j][cnt] == Computed) //Definition of Computed as above
    	return DP1[i][j][cnt];
        
	return DP1[i][j][cnt] = Prefix[i][j - 1] + min(Minim(i - 1, j, cnt), Minim(i - 1, j - 1, cnt - 1));
}

Note the use of \text{INF}, as opposed to the use of -\text{INF} in the previous code, as this asks for min, while the other code asked for max. Also, DP1 has been used to differentiate it from DP in the previous code.

Using this, we can efficiently determine the best possible Path-Sum between two starting indices p_1 and p_2.

A simple O(M^2) loop should check every valid pair of starting indices, for the maximum possible Path-Sum. This is achievable by using the following equation to find the maximum possible Path-Sum between any two indices p_1 and p_2(p_1 < p_2).

\text{PathSum}[p_1][p_2] = \text{DP}[N-1][p_2][K] - \text{DP1}[N-1][p_1][K]

You may wonder, ā€œwonā€™t there be a case when \text{DP}[N-1][p_2] and \text{DP1}[N-1][p_1] needs less than K moves to achieve itā€™s max/min?ā€ Yes!
This has been covered in this part above.

Note that exactly \text{cnt} moves of type (i-1,j-1) may not be required to achieve the maximum in the current recursive call, as we are only trying to maximise the overall sum, and not the number of (i-1,j-1) moves (while remaining within the valid range).

So, our recurrence only calculates the max possible sum using utmost (note the word utmost here) \text{cnt} \,\, (i-1,j-1) moves.

Seems like there are too many overhead calls in our top-down approach, resulting in a TLE. So lets map up a bottom-up approach.

Since Computing \text{DP}[i][j][\text{cnt}] requires us to compute both \text{DP}[i-1][j][\text{cnt}] and \text{DP}[i-1][j-1][\text{cnt}-1], thus row i must be computed before going to i+1 (so computing i is in the outermost loop). Then for every column j in i, 0 \le \text{cnt} \le K must be calculated. Thus computing j is in the middle loop and computing \text{cnt} is in the innermost loop.

It could be the other way too(\text{cnt} then j), but this is my preference. Proof of why this part is required is left to the reader.

Therefore, the bottom-up approach to calculate \text{DP}[i][j][\text{cnt}] would be:

for(i = 0; i < N; i++)
    for(j = 0; j < M; j++)
        for(cnt = 0; cnt <= K; cnt++)
            DP[i][j][cnt] = Prefix[i][j] + max(DP[i - 1][j][cnt],DP[i - 1][j -  1][cnt - 1]);

You can do similarly for the \text{DP1}[i][j][\text{cnt}] also.

What about the base cases? They are as follows:

  • \text{DP}[0][j][\text{cnt}] is \text{Prefix}[0][j] for every value of \text{cnt} (Since we want to use utmost \text{cnt} (i-1,j-1) moves).
  • \text{DP1}[0][j][\text{cnt}] is \text{Prefix}[0][j-1] for every value of \text{cnt}.
  • \text{DP}[i][0][\text{cnt}] (i > 0) is \text{DP}[i-1][0][\text{cnt}] + \text{Prefix}[i][0] for every value of i.

SOLUTION SNIPPET:

//Calculate DP[][][]
for(i = 0; i < N; i++){
    for(j = 0; j < M; j++){
        for(cnt = 0; cnt <= K; cnt++){
            DP[i][j][cnt] = Prefix[i][j] + max(DP[i - 1][j][cnt], DP[i - 1][j -  1][cnt - 1]);
        //Invalid case's(out-of-bounds) and base case should be handled.
        }
    }
}

//Calculate DP1[][][]
for(i = 0; i < N; i++){
    for(j = 0; j < M; j++){
        for(cnt = 0; cnt <= K; cnt++){
            DP1[i][j][cnt] = Prefix[i][j - 1] + min(DP1[i - 1][j][cnt], DP1[i - 1][j -  1][cnt - 1]);
        }
    }
}

ans = -INF;
//O(M^2) loop to check for the 2 best starting cells
for(j = 0; j < M; j++){
    for(j1 = j + K + 1; j1 < M; j1++){
        //Note j < j1
        ans = max(ans, DP[N - 1][j1][K] - DP1[N - 1][j][K]); 
    }
}

cout << ans << endl;

TIME COMPLEXITY:

Computing \text{Prefix}[N][M] takes O(N*M).

Since the unique states in the DP are [N][M][K+1] and each computation is O(1), computing takes O(N*M*K).

Final checking over all possible pairs of p_1, p_2 is O(M^2) .

\therefore Total time complexity is

O(N*M + N*M*K + M^2)

MEMORY COMPLEXITY:

The grid requires O(N*M) space. The DP and DP1 arrays require O(N*M*(K+1)) memory each. The total memory requirement is therefore

O(N*M + 2*N*M*K) \approx O(2*N*M*K)

SOLUTIONS:

Editorialistā€™s solution can be found here.

SIMILAR PROBLEMS:

Comb 46E

Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!

Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome :star_struck: editorial)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

Also donā€™t forget to up-vote this post if you liked it ! :smile:

11 Likes

I have a problem with ā€˜Kā€™ , whenever cnt>K, it stops doing it, but whats the guarantee that the previous ā€˜Kā€™ are all the best ?

It may happen, that we should use ā€˜K-1ā€™ only, and use the last one only at some end timeā€¦how does the code handles that case ?

In short:- How do you make sure that the K positions you selected to go to (i-1,r-1) are the best positions ?

By this statement, are you asking for the proof that the recurrence relation indeed maximises \text{DP[r][c][cnt]}?
Or have I misunderstood your question and do you refer to something else?

Yes, you are correct I want the proof if it maximizes the stuff? Though I know it does as its AC but I wanna know why mainly due to the ā€˜Kā€™ part. Thanks for the concern :slight_smile:

Did you understand this recurrence? This is a simple recurrence and I assume you donā€™t have any problem understanding this(if you do, please go through the pre-requisites once :smile:)

Now lets start by proving the base case, i.e, r = 0. The answer to this query is \text{Prefix}[0][c], which is the maximum, as there are no rows above this row, and both \text{Maxim}(0 - 1, c, cnt) and \text{Maxim}(0 - 1, c - 1, cnt - 1) should return 0.

Now assume \text{DP}[r][c][cnt] is true for all \{c, cnt\} for some row r.
Now for row r + 1, some column c_1 and some cnt_1, the recurrence tryā€™s to find the maximum between \text{DP}[r][c_1][cnt] and \text{DP}[r][c_1 - 1][cnt - 1] and adds to it the prefix sum \text{Prefix}[r+ 1][c_1].
Note that since from (r + 1, c_1) the only possible cells I could move to next were (r, c_1) and (r, c_1 -1), and the max of both of these were calculated correctly(according to our assumtion), the maximum possible of \text{DP}[r + 1][c_1][cnt] has also been computed correctly.
The base case has been proved above, thus, the recurrence relation has been proved true.
I hope you could understand something from this. If not, read a bit about recurrence relations. Youā€™ll be able to understand this better then :smile:.

1 Like

Areeā€¦donā€™t worry, I am well versed with dp and recurrence stuffšŸ˜‚

Then why did you want the proof for the recurrence relation?

1 Like

Something just didnā€™t feel right to me for ā€˜Kā€™. Now, I am feeling its all right.

1 Like

Iā€™ll disturb you a bit more tomorrow, for the Binary Movements stuff as I had some doubt in it 2 months agoā€¦hope you donā€™t mind. All your beautiful editorials are archive problems for me :stuck_out_tongue:

I have no problem. That was my first editorial, and Iā€™ll be waiting for your doubts :stuck_out_tongue:

1 Like

I dont know why but I feel as Binary Movements is the hardest coding problem on the planetšŸ˜„ I had nightmares related to it.
Kudos to you! You bravely solved it! :stuck_out_tongue:

1 Like