PROBLEM LINKS
DIFFICULTY
SIMPLE
PREREQUISITES
Dynamic Programming
PROBLEM
There is an N × N matrix. The cells in this matrix are numbered [1][1] through [N][N]. Each cell [i][j] contains an integer S[i][j]. A path is defined as a sequence of cells that starts on the top left cell (cell [1][1]), moving only rightwards or downwards, and ends on the bottom right cell (cell [N][N]). Cyael wants to find a path with the maximum average value of all integers on the path, excluding the first and the last cells. Help her.
QUICK EXPLANATION
The number of cells on any path is constant, i.e., 2N-3. Therefore, we can just find a path with the maximum total values of all integers on the path, and then divide the maximum total values by the number of cells.
This becomes a classical dynamic programming problem. Let dp[i][j] be the maximum total values of any path from [1][1] to [i][j]. The recurrence is dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + S[i][j], with dp[i][j] = -infinity for i < 1 or j < 1. The base case is dp[1][1] = S[1][1].
The answer to this problem is the maximum average value = dp[N][N] / (2N-3).
EXPLANATION
First, let’s count how many cells Cyael will pass in any path. It turns out that this number is always constant, i.e., 2N-1. An easy way to see this is as follows. In any path, Cyael must move rightwards exactly (N-1) times and downwards exactly (N-1) times to get to cell [N][N]. Therefore, the number of cells is 1 + (N-1) + (N-1) = 2N-1. Excluding the first and the last cells, the number of cells is 2N-3.
Since the number of cells on any path is constant, we can simplify the problem into finding a path with the maximum total values instead of the average. In the end, we can divide the answer with 2N-3 to get the average value.
The simpler problem can be solved using dynamic programming. The state consists of two values: the current row and the current column. Let dp[i][j] be the maximum total values of any path from [1][1] to [i][j]. There are (at most) two possibilities:
- The path with the maximum total value goes from cell [1][1] to cell [i-1][j], and then downwards to cell [i][j]. The maximum total value is dp[i-1][j] + S[i][j]. This can happen when i > 1.
- The path with the maximum total value goes from cell [1][1] to cell [i][j-1], and then rightwards to cell [i][j]. The maximum total value is dp[i][j-1] + S[i][j]. This can happen when j > 1.
The base case is when we are on the first cell of the path. dp[1][1] = S[1][1].
As we want to maximize the total value, we get the recurrence dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + S[i][j]. Note that in this recurrence, dp[i-1][j] and dp[i][j-1] may refer to non-existing cells. We can fix this by improving the recurrence into:
dp[i][j] =
- S[1][1], if i = 1 and j = 1
- dp[i-1][j] + S[i][j]; if j = 1
- dp[i][j-1] + S[i][j]; if i = 1
- max(dp[i-1][j], dp[i][j-1]) + S[i][j]; otherwise.
Another easy way is to assign dp[i][j] = -infinity if i < 1 or j < 1. Because we don’t have infinity in any programming language, we can assign dp[i][j] to a value that is smaller than any value in the DP table. The minimum value is -2500 × (2N-3), so we can assign safely to for example -1,000,000,000.
The time and space complexity of this problem is O(N2).
Here is a pseudocode of this solution:
read(N)
for i = 1; i ≤ N; i++:
dp[0][i] = dp[i][0] = -1000000000
for i = 1; i ≤ N; i++:
for j = 1; j ≤ N; j++:
read(S[i][j])
if 1 = 1 and j = 1:
dp[i][j] = S[i][j]
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + S[i][j]
print(dp[N][N] / (2N-3))
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.