AVGMAT - EDITORIAL

[taran_1407]

PROBLEM LINK:

Practice
Contest

Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Partial sums on a grid, implementation skills, and Manhattan distance. Visualization skills would be an advantage.

PROBLEM:

Given a N*M grid consisting of 0 and 1 only, Find the number of pairs of 1s in this grid having Manhattan distance x for every 1 \leq x \leq N+M-2.

SUPER QUICK EXPLANATION

• Notice that for a position, all positions at Manhattan distance x form a Diamond shape.
• Maintain Partial sums on diagonals, Iterate overall position for every length, counting the number of 1s lying at distance Length (on this diamond) in constant time using partial sums.
• Handle corners of diamond separately, and Indices carefully.

EXPLANATION

For this problem, Brute force solution would be to iterate over every pair of position and check if both positions contain 1. If yes, Increase Number of pairs with Manhattan distance x by 1, if x is Manhattan distance between both positions.

It can be referred in following pseudo-code.

for a in range (0, n):
	for b in range (0, m):
		for c in range(0,n):
			for d in range(0,m):
				//We are iterating over every pair of position
				//Current pair of position is ((a,b), (c,d))
				if grid[a][b] == 1 and grid[c][d]==1
					ans[abs(a-c)+abs(b-d)]++

Clearly, the above solution is of complexity O((N*M)^2) and thus, will time out for the last sub-task.

So, we need to optimize it. (Just see how many complications we like for getting AC :D)

As usual, Intensive Implementation problem ahead, you have been warned.

Suppose we approach the problem lengthwise.

Consider position (x,y) in grid. List all positions in the grid which are at L Manhattan distance from this position.

This shape will automatically appear. So, If we count the number of 1s lying on this diamond in constant time, our problem is immediately solved.

But, The Important thing is, How to count?

The usual trick we used to do for find sum of sub-array when the array is static, that is Partial sums (Commonly used partial sums include Prefix arrays).

Now, we will split the diamond into 4 lines (We will handle corner points of diamond later). We will try to count the number of 1s lying on each line. For this purpose, we need partial sums on each diagonal of the grid. We have two type of diagonals, One from top left to bottom right (Called LTR (Left-to-Right) diagonal) and Top-Right to Bottom Left (Called RtL diagonal). We can see that line 1 and 3 in the image is of type RTL while line 2 and 4 in the image are of type LtR.

After we get the number of 1s on each line, we can see that if there is 1 on any corner point, it will be counted twice, so, we check if corner point as 1, and if yes, exclude it once to get the accurate count.

Now, the Final answer will contain double the number of pairs with Manhattan distance x for every 1 \leq x \leq N+M-2 Since each pair is counted twice, So, just divide final answers by 2.

Since this is an implementation problem, I am sharing a few implementation points too.

Building partial sum arrays on diagonal.

Click to view

Consider we are making for Diagonal of type LtR first. Recurrence for building LtR partial sum grid is LR[i][j] = g[i][j] + LR[i-1][j-1]. This way, LR[i][j] represent number of 1s on diagonal of type LtR ending at (i,j).

For partial sum grid of type RtL, recurrence is RL[i][j] = g[i][j]+RL[i-1][j+1]

For Handling lines, a picture for understanding.

Click to view

I know that problem still require careful implementation to avoid Index out of bounds error, but that’s what an implementation problem is.

Implementaton

First of all, the preprocessing matrix can be reflected as follows.

Every position ltr[x][y] and rtl[x][y] contains the sum of elements, which are passed by the arrow to reach position (i,j). This array can be simply calculated using recurrences I mentioned above.

Very very Important part about these matrices, is to learn how to move z positions up and down. (0-based indexing in the grid).

For LTR matrix, each red diagonal satisfies y = x+C for some constant C ranging from -N+1 to M+1. If any point has y-x outside this range, The diagonal crossing that point can never touch grid at all and can be ignored. Suppose we are at (x, y) and want to move two steps downward, to include z cells on same diagonal in next z rows. We know, the new X coordinate will be x+z. New y coordinate is (x+z)+C.

For RTL matrix, each red diagonal satisfies y = -x+C for some constant C ranging from 0 to N+M-2. If any point has x+y outside this range, The diagonal crossing that point can never touch grid at all and can be ignored. Suppose we are at (x, y) and want to move z step downward, to include z cells on same diagonal in next z rows. We know, new X-coordinate will be x+z. New y coordinate is (x+z)-C.

Be sure to understand this part, only then next will make sense.

Let’s start actual counting of pairs. Suppose we want to calculate the number of 1s lying on Diamond shape formed by all positions at Manhattan Distance L from (x,y).

We split the work into four diagonals of diamond, and use prefix sums. Out of the total diagonal shown image, we count only 1s lying on the red and blue part. But the red part is lying outside the grid, so cannot contain 1 at all. So, for every diagonal, we need the number of 1s lying on the blue part of diagonal.

For example, consider the following image, where the Current position is (4,4) and current length we are solving for is 2. We want to include the positions which have the arrow of color blue passing through them. This is for Two LTR diagonals. The red line is corresponding the imaginary position outside the grid, which is to the right (and bottom) to the current position, at distance L.

The yellow box is the first position in the matrix, which is lying on the path from our imaginary square. Since there cannot be 1 outside grid, the Yellow box will also contain the same number of 1s as the imaginary target box. Consider diagonal bottom to left only. We can find the coordinate of the bottom cell at L distance from (x,y) as (x+L, y) and we know, the yellow cell, lies inside the grid, so, may have min(N-1, x+L) row.

Now, you know one coordinate of the final position, as well as both coordinates of initial position, so, apply what we learned above, moving steps in the matrix.

A similar explanation holds for RTL matrix as well, except that directions are flipped.

(Just Flipped the previous image. xD)

Another thing, the above examples had only target point outside the grid. If the cell having a green arrow is outside grid, we can just ignore it because It can never have non-zero numbers of 1s.

I just cannot explain everything, so, in case you still find any difficulty, please refer solutions below, or ask in comments.

Time Complexity

For every length from 1 to N+M-2, Time to iterate over grid is O(N*M) each, So, overall Time complexity is O((N+M)*N*M). Other preprocessing is of order O(N*M).

So, Final time complexity is O((N+M)*N*M).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed.

[gorre_morre]

There is another interesting approach which is both pretty simple and have better time complexity, it also solves the problem for any distance function, it doesn’t have to be manhattan. With some intuition behind convolutions this problem can easily be solved by fft in O(N M (\log(N)+\log(M))). In matlab the code would just be something like

B = conv2(A,rot90(A,2))

where A is the matrix given in the input. B will be a histogram of all pairs having the same distance vector. Now you just need to sum up all vectors with the same length and you are done. Had matlab been a valid language for submission this problem could have been solved with around 5 lines of code. Here is my teams solution using numpy.

Btw if you want some explanation of convolutions and fft, I have previously written about it here. One way to understand the solution of this problem is think of the 1D case, more specific what is conv(A,reversed(A)).

[pshishod2645]

With fft it’s very very simple… just compute (\sum x^{x_i} y^{y_i}) (\sum x^{-xj} y^{-yj}), where (x_i, y_i) are co-ordinates of blocks having tree, and then you can easily compute the answer by taking sum of absolute powers of x and y.

To compute this 2-D convolution, I multiple powers of y by a big number N (N = 600), so the each (x_i, y_i) maps uniquely to different number so the convolution essentially became (\sum x^{x_i + y_iN}) (\sum x^{-(x_j + y_jN)})

[iprakhar22]

@gorre_morre “Btw if you want some explanation of convolutions and fft, I have previously written about it here.”

I guess you were about to put up any link there? If you were, could you, please? It would be very helpful. Thanks

[vijju123]

Forgot to add link in written about it here.

[gorre_morre]

oops, added the link now

[kingofnumbers]

We were aware of the fft solution, but if we increased the constraints people will complain that the problem is standard application of fft and there are no interesting ideas.

[arjan_bal]

Another option is to convert the co-ordinates into Chebyshev co-ordinates by scaling and rotating, and then solve the question for axis aligned squares

[robin999]

Click to view

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int n,m,s,i,j;
cin>>n>>m;
char a[n][m];
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>a[i][j];
}
}
s = n+m-2;
int res[s+1];
memset(res,0,sizeof(res));

	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			int k=0,l=0;
			int c=1;
			for(k=i;k<n;k++){
				for(l=0;l<m;l++){
					if(c==1)l=j,c++;
					int d ;
					d = abs(i-k)+abs(j-l);
					if(a[i][j]=='1' && a[k][l]=='1' && d!=0){
						res[d]++;
					}
					
				}
			}
			
		}
	}
		for(i=1;i<=s;i++){
			cout<<res[i]<<" ";
		}cout<<"\n";
}
return 0;

}

Why this code of mine gives tle on subtask-2 ,
help please…

[naveen_yadav]

why im getting wrong answer for this solution… i compressed it to O(N*M)
https://www.codechef.com/viewsolution/21064331

[taran_1407]

Nice trick

Can you provide some reference, which may be helpful?

[taran_1407]

Your program has complexity O((N*M)^2) which naturally times out.

[taran_1407]

I think you should change in the last loop, to iterate over the whole list in both loops. Then you’ll get AC for first subtask, while TLE for second.

For solving 2nd subtask, refer editorial.

[brainfreeze]

I have a slightly different approach with the same complexity. Let’s note that if we have two points A and B and B is lower (or at the same level, actually) than A, then the Manhattan distance between them is either difference between sums of their coordinates (dist=abs((bx+by)-(ax+ay)) if B is down and to the right from A) or difference between differences of their coordinates (dist=abs((bx-by)-(ax-ay)) if B is down and to the left from A). If B is straight down from A it is obvious that both formula will return the same result.

Knowing that we can construct 2D prefix tables for each possible sum and each possible difference in coordinates (PTS[s][i][j] stores number of 1s in the rectangle ((1,1),(i,j)) which have sum of coordinates s, PTD[d][i][j] - number of 1s in the same rectangle with difference d (note that the difference can be negative))

That’ preprocessing with complexity O(nm(n+m)).

Now the solution itself:

We can iterate over all points (process rows top to bottom, points in a row left to right) and note that all points processed previously fit in two rectangles. If we are at point (x,y) then rectangles are ((1,1),(x-1, y)) and ((x,1),(m, y-1))(either rectangle may be nonexistent depending on x and y).

Using our observation from the beginning we may note that for every point in the first rectangle distance from (x,y) to it is the difference between sums of coordinates and it is difference between differences for the second rectangle.

Thus instead of iterating over every previous point (in quadratic time) we can iterate over every sum and difference instead in linear time (for example if we are now processing a point (5,3) and first rectangle have 3 points with sum of 4 (we get this info in O(1) from our prefix tables) we just add 3 to the count of distance (5+3)-4=4, regardless of where exactly in the rectangle those points are).
Solution itself, like preprocessing, takes O(nm(n+m)).

[taran_1407]

Nice idea, would be better to share solution link.

[aman_robotics]

My solution for this problem was a little different. The idea was to process the matrix row wise from top to bottom . We have a ans[] array which stores the answer for all the possible pairs with distance between 1 and N + M -2 . So first of all we update our ans array for all possible Manhattan distances for each row .
We need one more 3-d array for pre-computation freq[][][] which stores the number of pairs with Manhattan distance d for all the rows above and equal to it.

Now the solution :

1. Say we are at index(i, j), we need all the pairs of cells which are at a distance d (where 1 <= d <= N + M - 2 ). So for this we just need to go to freq[i - 1][j] and we can get the answer for freq[i][j] . How ?.. So freq[i][j][k] = freq[i][j][k - 1] i.e. the number of cells at distance k from the cells would be obviously number of cells at distance k - 1 for a cell at index(i - 1, j). Only freq[i]j = 1, if arr[i - 1][j] = 1.
2. Now if arr[i][j] = 1, then we update the ans[] array by freq[i][j][k]. Now we update the freq[i][j][k] for all the cells with distance k in the same row.
3. Solution

Sorry for my poor English, and point out if you don’t understand any point.

[meooow]

I have used the same approach. (x, y) \rightarrow (x - y, x + y) is one way to do it.

[ayush1111]

https://www.codechef.com/viewsolution/21092301, Can Somebody tell me my code complexity, I think its O(TNM) but it gets TLE.

[taran_1407]

This solution has complexity O((N*M)^2).

[mightymercado]

Team FFgacha has an amazingly short solution with O(nm(n+m)) time with O(n*m) space complexity. https://www.codechef.com/viewsolution/21054988