 # MGCRNK - Editorial

Practice

Contest

SIMPLE

## PREREQUISITES

Dynamic Programming

## PROBLEM

There is an N × N matrix. The cells in this matrix are numbered  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 ), 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  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 = S.

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  to [i][j]. There are (at most) two possibilities:

• The path with the maximum total value goes from cell  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  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 = S.

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, 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[i] = dp[i] = -1000000000

for i = 1; i ≤ N; i++:
for j = 1; j ≤ N; 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.

4 Likes

#include <stdio.h>
#include <stdlib.h>
void max(int b , int a , int i ,int j , int s , int n){
int c=0 , r=0;
if((i<=n)&&(j<=n)){
c=s+a[i][j+1];
r=s+a[i+1][j];
if(c>=r){
b[i][j+1]=1;
j=j+1;
max(b ,a ,i ,j ,c ,n);
}
else{
b[i+1][j]=1;
i=i+1;
max(b , a ,i ,j ,r , n);
}
}

}

int main()
{
int i ,j ,a ,n , b ,s=0 ,t ;
scanf("%d" , &t);
while(t–){
float d=0;
s=0;
scanf("%d" , &n);
for(i=1;i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d" , &a[i][j] );
b[i][j]=0;
}
}
max(b , a , 1 ,1 , s, n);
a=0;
a[n][n]=0;
for(i=1; i<=n; i++){
for(j=1; j<=n ;j++){
if(b[i][j]==1){
d=d+a[i][j];
}
}
}
if(d>=0){
printf("%.7lf\n" , d/(2*n-3));
}
else{

}}

}

#include <stdio.h>
#include <stdlib.h>
void max(int b , int a , int i ,int j , int s , int n){
int c=0 , r=0;
if((i<=n)&&(j<=n)){
c=s+a[i][j+1];
r=s+a[i+1][j];
if(c>=r){
b[i][j+1]=1;
j=j+1;
max(b ,a ,i ,j ,c ,n);
}
else{
b[i+1][j]=1;
i=i+1;
max(b , a ,i ,j ,r , n);
}
}

}

int main()
{
int i ,j ,a ,n , b ,s=0 ,t ;
scanf("%d" , &t);
while(t–){
float d=0;
s=0;
scanf("%d" , &n);
for(i=1;i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d" , &a[i][j] );
b[i][j]=0;
}
}
max(b , a , 1 ,1 , s, n);
a=0;
a[n][n]=0;
for(i=1; i<=n; i++){
for(j=1; j<=n ;j++){
if(b[i][j]==1){
d=d+a[i][j];
}
}
}
if(d>=0){
printf("%.7lf\n" , d/(2*n-3));
}
else{