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;
}
