You are not logged in. Please login at www.codechef.com to post your questions!

×

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[i][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[i][j]
  • down[i][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[i][j], arr[i+1][j], $\dots$, arr[N][j]
  • right[i][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[i][j], arr[i][j+1], $\dots$, arr[i][M]

Based on above, can you derive the meaning of left[i][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[i][j-1] + right[i][j+1] + \underbrace{arr[i][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[i][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[i][j] &etc. to avoid counting errors for element at centre. (Think a little about it. A more detailed explanation is given in my corner :)

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

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 :)

Setter

View Content

Tester

View Content

Editorialist's Solution will be put up on demand.

$Time$ $Complexity-$ $O(N*M)$

CHEF VIJJU'S CORNER :D

1. Meaning of left[i][j]-

View Content

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

View Content

3. Setter's Notes-

View Content

4. Tester's Notes-

View Content

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.
This question is marked "community wiki".

asked 26 May '18, 18:47

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
accept rate: 18%

edited 12 Jun '18, 17:47

admin's gravatar image

0★admin ♦♦
19.7k350498541

The editorial link in the problem page is incorrect.

(27 May '18, 11:37) sarthakmanna6★

Will ping @admin

(27 May '18, 15:13) vijju123 ♦♦4★

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[i][j]. Then for all 4 directions, we just update it. Also while calculating the pre[i][j] for the last direction we create a min variable=-xxxxxxxxx,and while updating the pre[i][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

link

answered 26 May '18, 23:49

panik's gravatar image

5★panik
1127
accept rate: 7%

edited 27 May '18, 01:31

1

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!!

(27 May '18, 00:01) vijju123 ♦♦4★

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

link

answered 27 May '18, 15:55

shivam_g1470's gravatar image

4★shivam_g1470
556
accept rate: 7%

Thank you :) . 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 +)

(27 May '18, 17:50) vijju123 ♦♦4★

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

(27 May '18, 18:06) shivam_g14704★

Sorry, my bad.

(27 May '18, 18:31) vijju123 ♦♦4★

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)

(27 May '18, 19:04) vijju123 ♦♦4★

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

(27 May '18, 19:19) shivam_g14704★

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

link

answered 27 May '18, 00:08

anuj_2106's gravatar image

3★anuj_2106
1
accept rate: 0%

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

(27 May '18, 00:16) vijju123 ♦♦4★

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 code gives:

12

12

link

answered 27 May '18, 00:32

dushsingh1995's gravatar image

4★dushsingh1995
92113
accept rate: 11%

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.

(27 May '18, 15:13) vijju123 ♦♦4★

Can anyone help me in this solution :

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

link

answered 29 May '18, 17:28

vjvjain0's gravatar image

4★vjvjain0
9119
accept rate: 7%

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

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

link

answered 07 Jun '18, 04:52

hritikthube99's gravatar image

2★hritikthube99
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,085
×1,648
×145
×25

question asked: 26 May '18, 18:47

question was seen: 1,031 times

last updated: 12 Jun '18, 17:47