PLUS- Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Hasan Jaddouh
Tester- Jakub Safin
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY-MEDIUM

PRE-REQUISITES:

2-D Arrays, Maximum Sum contiguous subarray of a 1-D Array (i.e. Dynamic Programming ),Pre-calculation/Precomputation

PROBLEM:

Given a 2-D array of size N*M, you have to find the maximum value achievable by a + shaped pattern. The elements of the array can be negative.

QUICK EXPLANATION:

Key Strategy- Pre-computation of maximum possible sum of a contiguous sub-sequence (subarray) for each row and column, and then checking for each cell as a possible centre of + gets things done in O({N}^{2}).

We quickly pre-compute the maximum contiguous sub-sequence sum for each row and column, in 4 directions, namely, Up, Down, Left and Right. This can be done using the standard Maximum contiguous sub-sequence sum of a 1-D array. All thats left is, to check each cell as a possible centre of the + and use pre-computed data to find the value achieved by + shape in O(1). This leads to a O({N}^{2}) solution.

EXPLANATION:

This is a pretty much straightforward problem. The problem asks you to deduce that its an application of standard “Maximum sum of contiguous sub-sequence of 1-D array” problem and then implement it. This editorial will focus more on intuition and how to deduce the problem to the said contiguous sub-problem above. Implementation details can be seen in setter’s solution.

This editorial is having only a single section, as the approach is pretty much straight-forward and standard.

1. Setter’s Solution-

Lets start from the basics. How’d you write a brute force solution to this problem? One of the algorithms would be-

  1. For each cell A_{i,j} in the 2-D array, do the following-
  2. Set it as centre and compute the maximum contiguous sub-sequence sum in right direction.
  3. Compute the maximum contiguous sub-sequence sum in left direction
  4. Compute the maximum contiguous sub-sequence sum in upwards direction
  5. Compute the maximum contiguous sub-sequence sum in the downwards direction.
  6. Store the maximum value obtained and print it.

Clearly, this is O({N}^{3}) and a little bit hard to pass under 1sec time limit. Can we do something about it?

Note that, the maximum contiguous sub-sequence sum part is taking an O(N) time for each cell, making the solution time out. If we can, somehow, avoid re-computing the maximum contiguous sub-sequence sum again and again, we can get an AC.

Turns out, we can easily pre-calculate the required contiguous sub-sequence sums getting rid of the TLE!

What the setter did is, he made four 2-D arrays (1 for each direction). A little note on them could be helpful in getting the intuition,

  • up[j]* - Maximum sum contiguous sub-sequence of elements in upward direction, from rows 1,2,3,\dots,i More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[1][j], arr[2][j], \dots, arr[j]*
  • down[j]* -Maximum sum contiguous sub-sequence of elements in downward direction, from rows i,i+1,i+2,,\dots,N More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[j], arr[i+1][j], \dots, arr[N][j]*
  • right[j]- Maximum sum contiguous sub-sequence of elements in right direction, from columns j,j+1,j+2,\dots,M More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[j], arr[j+1], \dots, arr*[M]*

Based on above, can you derive the meaning of left[j]* ? (answer will be in Chef Vijju’s Corner :D)

I highly stress that the meanings of each of these arrays are clear to you. The pre-computation uses standard 1-D array algorithm, which you can see from the link in pre-requisite, or check from setter’s solution. Discussing it would be redundant in the editorial.

The next part is, deriving answer for the + shape centered at A_{i,j} from this pre-computation. If the meaning of the above arrays are clear to you, it will not be hard at all!

Let Ans_{i,j} represent the maximum value of the + sign centered at cell A_{i,j}. Then, we can say that-

Ans_{i,j}= up[i-1][j] + down[i+1][j] + left*[j-1] + right*[j+1] + \underbrace{arr*[j]} _ {Adding\space value\space at\space centre\space of\space +}

What this formula does is, it will find the maximum contiguous sub-sequence sum in all four directions, excluding the cell A_{i,j}. The meaning of arrays representing directions (Eg- up*[j]) is already given above, and you can refer to that for interpretation purposes. Note that, we used up[i-1][j] instead of up[j] &etc. to avoid counting errors for element at centre.* (Think a little about it. A more detailed explanation is given in my corner :slight_smile:

At last, we will print the maximum Ans_{i,j} we get, and print it :slight_smile:

SOLUTION:

For immediate availability of setter and tester’s solution, they are also pasted in the tabs below. This is for your reference, and you can copy code from there to wherever you are comfortable reading them. You now dont have to wait for @admin to link solutions :slight_smile:

Setter

Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
			
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'

‘);
}
string readStringLn(int l,int r){
return readString(l,r,’
‘);
}
string readStringSp(int l,int r){
return readString(l,r,’ ');
}

int up[1010][1010];
int dn[1010][1010];
int lft[1010][1010];
int rgt[1010][1010];
 
int n,m;
int arr[1010][1010];
int T;
int sm_n=0,sm_m=0;
 
int main(){
	//freopen("05.txt","r",stdin);
	//freopen("05o.txt","w",stdout);
	T=readIntLn(1,100);
	while(T--){
		n=readIntSp(3,1000);
		m=readIntLn(3,1000);
		sm_n += n;
		sm_m += m;
		assert(sm_n <= 1000);
		assert(sm_m <= 1000);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(j==m){
					arr*[j] = readIntLn(-100000,100000);
				} else {
					arr*[j] = readIntSp(-100000,100000);
				}
			}
		}
		for(int i=1;i<=n;i++){
			lft*[1] = arr*[1];
			for(int j=2;j<=m;j++){
				lft*[j] = max(lft*[j-1] + arr*[j],arr*[j]);
			}
		}
		for(int i=1;i<=n;i++){
			rgt*[m] = arr*[m];
			for(int j=m-1;j>=1;j--){
				rgt*[j] = max(rgt*[j+1] + arr*[j],arr*[j]);
			}
		}
		for(int j=1;j<=m;j++){
			up[1][j] = arr[1][j];
			for(int i=2;i<=n;i++){
				up*[j] = max(up[i-1][j] + arr*[j],arr*[j]);
			}
		}
		for(int j=1;j<=m;j++){
			dn[n][j] = arr[n][j];
			for(int i=n-1;i>=1;i--){
				dn*[j] = max(dn[i+1][j] + arr*[j],arr*[j]);
			}
		}
		int sol = -1ll<<30;
		for(int i=2;i<=n-1;i++){
			for(int j=2;j<=m-1;j++){
				sol = max(sol, up[i-1][j] + dn[i+1][j] + lft*[j-1] + rgt*[j+1] + arr*[j]);
			}
		}
		cout<<sol<<endl;
	}
	assert(getchar()==-1);
} 

Tester

Click to view
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge
 
using cat = long long;
 
#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif
 
int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int T;
	cin >> T;
	for(int t = 0; t < T; t++) {
		int N, M;
		cin >> N >> M;
		vector< vector<int> > G(N, vector<int>(M));
		for(int i = 0; i < N*M; i++) cin >> G[i/M][i%M];
		vector< vector<cat> > mx_up(N, vector<cat>(M));
		vector< vector<cat> > mx_down(N, vector<cat>(M));
		vector< vector<cat> > mx_lft(N, vector<cat>(M));
		vector< vector<cat> > mx_rt(N, vector<cat>(M));
		for(int i = 0; i < N; i++) {
			cat mi = 0, sum = 0;
			for(int j = 0; j < M; j++) {
				if(j > 0) mx_lft*[j] = sum-mi;
				mi = min(mi, sum);
				sum += G*[j];
			}
			mi = sum = 0;
			for(int j = M-1; j >= 0; j--) {
				if(j < M-1) mx_rt*[j] = sum-mi;
				mi = min(mi, sum);
				sum += G*[j];
			}
		}
		for(int i = 0; i < M; i++) {
			cat mi = 0, sum = 0;
			for(int j = 0; j < N; j++) {
				if(j > 0) mx_up[j]* = sum-mi;
				mi = min(mi, sum);
				sum += G[j]*;
			}
			mi = sum = 0;
			for(int j = N-1; j >= 0; j--) {
				if(j < N-1) mx_down[j]* = sum-mi;
				mi = min(mi, sum);
				sum += G[j]*;
			}
		}
		cat ans = -OVER9000;
		for(int i = 1; i < N-1; i++) for(int j = 1; j < M-1; j++)
			ans = max(ans, G*[j] + mx_down*[j] + mx_up*[j] + mx_lft*[j] + mx_rt*[j]);
		cout << ans << "

";
}
return 0;}

// look at my code
// my code is amazing

Editorialist’s Solution will be put up on demand.

Time Complexity- O(N*M)

CHEF VIJJU’S CORNER :smiley:

1. Meaning of left[j]*-

Click to view

left[j]- Maximum sum contiguous sub-sequence of elements in left direction, from columns 1,2,3, \dots,j More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[1], arr*[2], \dots, arr*[j]**

2. Note on counting errors and using, say, up[i-1][j] instead of up[j]*

Click to view

The value of element at the centre MUST be a part of the value/answer. We cannot say for certain, however, that it will be included in maximum contiguous sub-sequence sum for any direction. Maximum sub-array algorithm will, chose an element only if it maximizes the sum in that direction. It nowhere guarantees that the element we are using as centre will be picked. It is possible that none of the four include it in maximum sum calculation for the respective directions (undercount error) and its also possible that ALL of them count it while calculating the sum (overcount error).

3. Setter’s Notes-

Click to view

Try each possible center, for each one you should find maximum sum in each direction, naively this is O({N}^{3}) (assuming N=M), but you can precalculate the max sum from each cell to each of the 4 direction using similar idea to standard problem "maximum sum sub-array 1-D"

4. Tester’s Notes-

Click to view

O(N*M) algorithm would be to compute the max. sum going up/down/left/right by applying the standard linear time algorithm to each row/column and then compute the answer by trying all central cells and adding the max. in each direction.

5. Some related practice problems are below-

  • Painting a Town - A challenging problem from ICPC-Kharagpur regions. Needs knowledge of DFS on a matrix, and probability as well.
2 Likes

I suggest that instead of making 4 2D arrays for precomputation, we can make one 2D array. First we copy the original array to the pre*[j]. Then for all 4 directions, we just update it. Also while calculating the pre*[j] for the last direction we create a min variable=-xxxxxxxxx,and while updating the pre*[j] we just compare it with the each element and print the max. I think this would save a lot of memory as well as aa little time too.
My solution- https://www.codechef.com/viewsolution/18665680

1 Like

@vijju123 Could you please provide some more problems involving this concept?

For those who are getting wrong answer on second testcase of first subtask, initialize ans = INT_MIN.

Weak testcases. Consider this testcase:

2

3 4

2 2 2 2

2 2 2 2

2 2 2 2

3 3

2 2 2

2 2 2

2 2 2

Output should be:

12

10

But my


[1] gives:

12

12


  [1]: https://www.codechef.com/viewsolution/18670333

hey, It was a pretty straightforward explanation. Thank You. Would you also be kind enough to point out the mistake in my solution for first Subtask#1 for 20 points? Thanks in advance. I tried following brute force approach.
You can find my code at https://www.codechef.com/viewsolution/18668975

1 Like

Can anyone help me in this solution :

https://www.codechef.com/viewsolution/18695286

although my code has O(n^2) complexity it is giving TLE!!!
Thanks in advance!

https://www.codechef.com/viewsolution/18807695

Yes, that is also possible. I wanted to try it out, but I had no time, so had to stick with setter’s solution. Thanks for sharing!!

1 Like

The real concept used is simple pre-computation and 1-D max sub-array sum. Which of these do you want?

The editorial link in the problem page is incorrect.

I feel your code suffers from run-time error and undefined behavior for that case. If thats true, we cant do much for that, as making cases against undefined behavior for too many instances seems tedious.

Will ping @admin

Thank you :slight_smile: . One of the few people who gave feedback on quality of editorial ^_^.

Check out this Test case-

Input 1 3 5 0 -1 0 0 0 1 0 -1 0 -1 0 0 0 0 0 Your Output 0 Expected Output -1 (All 3 possible locations give -1 as sum of +)

if the centre is at (1,2) ie -1, left arm till 1, right till 0, upper and down till 0. the sum of plus will be zero. @vijju123
Also, Many AC submission are also giving 0 as solution, example: https://www.codechef.com/viewsolution/18668969

Sorry, my bad.

Here.

Input 1 3 5 1 1 1 -100 -100 -1 1 -1 -1 10 1 1 1 1 1 Your Output 1 Expected Output 11 Error probably here- if((i+l<n-2)) (line 46)

It was indeed that line and another line somewhere below it. I was checking 1 less index. Thank You.