can anyone explain the logic behind the above question for the larger test case
Try using diagonal sums. Notice that the locus of all the points which are at a distance d from a certain point (say (x,y) )is the perimeter of a square of diagonal length 2d centred at (x,y). This hints at using diagonal prefix sums to compute the number of valid cells for each valid point.
Implementation: https://www.codechef.com/viewsolution/21006413
can u explain a bit more
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))
B is now 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.
If you need some explanation of convolutions and fft, I have previously written about it here.
A very useful trick while dealing with Manhattan distances is to transform (x,y) coordinates to (x+y,y-x) . Now in this new Coordinate system , the locus of all points which are at distance “d” is a “SQUARE”. Actually, in general this is just rotation of axes by 45 deg , due to which the diamond shape locus of Manhattan distance is translated to Square shaped .
1 Like
you can apply partial sums on diagonals directly, instead of making this transfer then making partial sums on rows and columns
1 Like