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)})
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
#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…
why im getting wrong answer for this solution… i compressed it to O(N*M)
https://www.codechef.com/viewsolution/21064331
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)).
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 :
Sorry for my poor English, and point out if you don’t understand any point.
https://www.codechef.com/viewsolution/21092301, Can Somebody tell me my code complexity, I think its O(TNM) but it gets TLE.
Team FFgacha has an amazingly short solution with O(nm(n+m)) time with O(n*m) space complexity. CodeChef: Practical coding for everyone
@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 
Forgot to add link in written about it here. 
oops, added the link now
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.
Nice trick
Can you provide some reference, which may be helpful?
Your program has complexity O((N*M)^2) which naturally times out.
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.
Nice idea, would be better to share solution link.
I have used the same approach. (x, y) \rightarrow (x - y, x + y) is one way to do it.
This solution has complexity O((N*M)^2).
Yup, I did it the same way as meooow, basically you have to rotate the coordinates by 45 degrees, then scale them by multiplying by sqrt(2), so the sqrt(2) from the numerator and denominator cancel out. As to why 45 degrees and sqrt(2), you’ll have to compare circles in both co-ordinate systems to get the answer