FARHOSTEL - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Tarun Arora
Tester: Jeevan Jyot Singh, Nishank Suresh
Editorialist: Tarun Arora

DIFFICULTY:

2441

PREREQUISITES:

Prefix Sums, Dynamic Programming

PROBLEM:

Given two matrices A and B, of size N*M. The value in each cell denotes the count of students currently in that cell.

  • Students represented by matrix A want to reach the left-edge of the field moving only leftwards.
  • Students represented by matrix B want to reach the top-edge of the field moving only upwards.

The paths followed by two students going to different hostels should not intersect.

Calculate the maximum number of students which can reach their hostels.

EXPLANATION:

The given problem can be solved by using two-dimensional dp speeded up with prefix sums with O(M*N) time complexity and O(m*n) extra space for the dp matrix.

Now we need to make the partition of the field to maximize the number of students, so this would be step-like structure starting from the top-left end towards the bottom-right end.

Preprocessing: For both matrices A and B, for every column calculate the prefix sums, such that:

  • A[i][j]=A[i][j]+A[i+1][j]...+A[n-1][j]
  • B[i][j]=B[0][j]+B[1][j]+...+B[i][j].

Now we would start building our dp[m+1][n+1] matrix from the last column and from bottom to top for every column, and the formula for dp[row][col] is

  • dp[row][col]=max(dp[row+1][col], dp[row][col+1]+A[row-1][col]+B[row][col])
    (Note: elements going out of the matrix would be equal to 0)

dp[row][col] denote the maximum number of students who could reach their hostels when the submatrix (row...n)*(col...m) is considered.

Now, The maximum number of students that would reach their hostels would be equal to dp[0][0].

TIME COMPLEXITY:

O(N*M) for each test case.

SOLUTION:

Setter's/Editorialist's solution
#include "bits/stdc++.h"
using namespace std;

typedef long long        ll;
const unsigned int M = 1000000007;

vector<vector<ll>> dp;

ll calcStudents(vector<vector<ll>>& A, vector<vector<ll>>& B){
    int n=A.size();
    int m=A[0].size();
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<m;j++){
            A[i][j]+=A[i+1][j];
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            B[i][j]+=B[i-1][j];
        }
    }
    vector<vector<ll>> dp(n+1, vector<ll>(m+1));
    for(int col=m-1;col>=0;col--){
        for(int row=n;row>=0;row--){
            dp[row][col]=0;
            if(col<m-1)dp[row][col]+=dp[row][col+1];
            if(row)dp[row][col]+=B[row-1][col];
            if(row<n){
                dp[row][col]+=A[row][col];
                dp[row][col]=max(dp[row][col],dp[row+1][col]);
            }
        }
    }
    return dp[0][0];
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n, m;
        cin>>n>>m;
        vector<vector<ll>> A(n,vector<ll>(m));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>A[i][j];
        vector<vector<ll>> B(n,vector<ll>(m));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>B[i][j];
        cout<<calcStudents(A,B)<<"\n";
    }
    return 0;
}
1 Like

My solution looks like this how to optimise it using recursive approach help https://www.codechef.com/viewsolution/70135281

My first thought process was also the same. Time complexity of your code is O(n * m * m). You need to optimize the loop you are running in recursion.
You can go with the following recurrence,
f(i, j) = max( suff + pref + f(i + 1, j), f(i, j + 1) )
You can refer to my
submission

thanks buddy where I can find read more blogs or solve more question on these .
accepted code

Can someone please tell me how did you get the intuition to use DP here?

1 Like

my 3d 2nm DP sol
link: Solution: 70169743 | CodeChef

The idea is at every i,j we have two choices either sent all students((i+1,j),(i+2,j)…,(n-1,j)) to up hostel OR sent all students ((i,j+1),(i,j+2),…(i,m-1)) to left.
so we just try both ways for every index and choose maximum of then

6 Likes

I found your solution to be far more expressive and understandable than the tutorial’s :joy:

1 Like

:joy:
Glad that it helped :wink:

Guys can anyone explain the recursion logic? what exactly does
dp[row][col]=max(dp[row+1][col],dp[row][col+1]+A[row−1][col]+B[row][col])
mean.
@tarun_03_arora bhai kya hi explanation hey

Implemented after reading editorial
Memoised solution
DP solution

MISTAKE IN EDITORIAL!

(In the following reasoning, I use 0 indexing, assuming that the answer to the problem is dp[0][0])

In editorial author writes: “dp[row][col] denote the maximum number of students who could reach their hostels when the submatrix (row…n-1) * (col…m-1) is considered”. In general, it’s wrong! You can look at authors implementation and realise that in fact dp[row][col] denotes the maximum number of students who could reach their hostels when the submatrix (0…n-1) * (col…m-1) is considered AND (!!!) students on positions col, t…n-1 (I mean, students which are in column col and rows from [t; n - 1] (where t >= row)) go left and students which are “above” them (I mean, students which are in column col and rows from [0; t - 1]) go up. That’s why dp[row][col] = dp[row][col + 1] + A[row][col] (these guys go left) + B[row - 1][col] (these guys go up). So initially dp[row][col] means that exactly n - row lower students in column col go down and upper row students in this column go up.

And then we take dp[row][col] = max(dp[row][col], dp[row+1][col]) to take into account the cases when less students from column col go left and more go up (I mean, all such cases when exactly n - t lower students in column col go down and upper t students in this column go up, where t > row)

I ask the author to be more attentive. Less experienced participants than me won’t understand a damn thing at all, because one thing is written in the editorial, and another is implied. It also seems to me that the author’s analysis is not detailed enough. I hope I was able to explain it in more detail.

Thanks …I was searching two matrices AA and BB, of size N*MN∗M for my kid. Finally found it.

Can you elaborate it?