PROBLEM LINK:
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
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
SOLUTIONS:
Editorialistās solution can be found here.
SIMILAR PROBLEMS:
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 editorial)
- 1
- 2
- 3
- 4
- 5
0 voters
Also donāt forget to up-vote this post if you liked it !