# 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(N^{2}).

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.