Chefland and Average Distance logic needed

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