MGCRNK - Editorial

fushar · December 11, 2012, 6:26pm

PROBLEM LINKS

Practice

Contest

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²).

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.

satya753 · June 20, 2017, 11:02pm

#include <stdio.h>
#include <stdlib.h>
void max(int b[110][110] , int a[110][110] , 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[110][110] ,n , b[110][110] ,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[1][1]=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{
printf(“Bad Judges\n”);

}}

}

satya753 · June 20, 2017, 11:03pm

#include <stdio.h>
#include <stdlib.h>
void max(int b[110][110] , int a[110][110] , 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[110][110] ,n , b[110][110] ,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[1][1]=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{
printf(“Bad Judges\n”);

}}

}
*can someone tell me whats wrong with this code
**

harsh_1701 · January 7, 2024, 3:05pm

Hello Please help!!

Please check my solution . I have used memoization, I don’t know why it is giving wrong answer.

include <bits/stdc++.h>
using namespace std;
define endl (“\n”)
define pi (3.141592653589)
define mod 1e9 + 7
define ll long long
define vi vector
define vl vector
define pb push_back
define mp make_pair
define ff first
define ss second
define all(c) c.begin(), c.end()
define rrep(i, n) for (int i = n - 1; i >= 0; i–)
define rep(i, n) for (int i = 0; i < n; i++)
define loop(i, a, b) for (int i = a; i <= b; i++)
define fast
ios_base::sync_with_stdio(0), cin.tie(0);
define inf INT_MAX

ll solve(vector<vector> &arr,int n,int i,int j,vector<vector> &dp){
if(i>n || i<1 || j>n || j<1){
return 0;
}
if(i==n && j==n){
return 0;
}

if(dp[i][j] != inf){
    return dp[i][j];
}

ll case1 = solve(arr,n,i+1,j,dp);
ll case2 = solve(arr,n,i,j+1,dp);

ll result = max(case1,case2) + arr[i][j];

return dp[i][j] = result;

}

int main()
{
fast int t;
cin >> t;
cout<<fixed<<setprecision(8);
while (t–)
{
int n;
cin>>n;

    vector<vector<int>> arr(n+1,vector<int>(n+1,0));
    loop(i,1,n){
        loop(j,1,n){
            cin>>arr[i][j];
        }
    }
    
    vector<vector<ll>> dp(n+1,vector<ll>(n+1,inf));
    
    ll maxSum = solve(arr,n,1,1,dp);
    
    if(maxSum < 0){
        cout<<"Bad Judges"<<endl;
    }else{
        long double res = 1.0*maxSum/(2*n-3);
        cout<<res<<endl;
    }

}

return 0;

}