PROBLEM LINK:Setter: Hasan Jaddouh DIFFICULTY:EasyMedium 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+M2$. SUPER QUICK EXPLANATION
EXPLANATIONFor 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 pseudocode. 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(ac)+abs(bd)]++ Clearly, the above solution is of complexity $O((N*M)^2)$ and thus, will time out for the last subtask. 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 subarray 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 (LefttoRight) diagonal) and TopRight 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+M2$ 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. For Handling lines, a picture for understanding. ImplementatonFirst 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. (0based 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 $yx$ 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+M2$. 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 Xcoordinate 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(N1, 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 nonzero 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 ComplexityFor every length from $1$ to $N+M2$, 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 19 Oct, 05:34

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)). answered 21 Oct, 19:34
1
@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 :)
(21 Oct, 19:46)
1
Forgot to add link in
(21 Oct, 19:51)
1
oops, added the link now
(21 Oct, 19:51)

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((bxby)(axay)) 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),(x1, y)) and ((x,1),(m, y1))(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)). answered 22 Oct, 20:23

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 coordinates 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 2D 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)}) $ answered 21 Oct, 19:44

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 3d array for precomputation freq[][][] which stores the number of pairs with Manhattan distance d for all the rows above and equal to it. Now the solution :
Sorry for my poor English, and point out if you don't understand any point. answered 22 Oct, 21:23

Why this code of mine gives tle on subtask2 , help please... answered 22 Oct, 03:28

why im getting wrong answer for this solution.. i compressed it to O(N*M) https://www.codechef.com/viewsolution/21064331 answered 22 Oct, 10:44
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.
(22 Oct, 20:22)

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

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 answered 30 Oct, 06:45

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.