In the recent snackdown round A qualifier, there was a problem I could not figure out.
Link: https://www.codechef.com/SNCK1A19/problems/AVGMAT
From skimming the solutions and from making my own observations I have realized the following:
- Most solution use some type of DP with two passes storing DP1[i][j] and DP2[i][j], where i and j presumably mean row and column.
- For any given distance D, there are O(D) other nodes D away in manhattan distance
- We can construct ans from dp1 and dp2 where ans[i] stores the amount of pairs of nodes i away from each other in manhattan distance
The editorial is not out, as codechef editorials can be quite slow (some in 2016 still pending).
Can anybody explain the solution here?
EDIT:
Possible solutions:
Prefix sums over diagonals (previous mentioned observation), dp1[][] and dp2[][] represent theses where each of them deal with a diagonal in each direction
Rotate the matrix by 45 degrees. Now you can solve it with normal prefix sums (over columns and rows) or matrix sums because the distance will be a "square away". One such conversion method is mat[x][y] --> mat[x-y][x+y]. Note that this conversion is space inefficient, and therefore you may need to define a NxN matrix as mat[-n...n][0...2n]
FFT and mathy approaches .-.
But editorial is actually out?
I think the best solution is to rotate the coordinates 45 degrees, so (X, Y) becomes (X+Y, X-Y). Now (old manhattan distance) = (new chebyshev distance). Wiki link
So we can imagine the chebyshev distance range from a house as a square, and keep expanding the square, and count new houses in each expansion. We have O(N*M) houses, and we do O(N) (or O(M)) square expansion for each house. This gives O(N^3) or so so
Sorry I don't use codechef often (actually I never used before this contest) so I'm not so sure about how their website it organized.
Although I am quite shocked that search of "snackdown a19 editorial" on google brought nothing.
Where do you find these? Because it's also not linked to the contest itself...
Just google the contest code + "editorial". "SNCK1A19 editorial" brings up the AVGMAT tutorial as the fourth result for me.
Hey MidoriFuse, Is expanding the square one at a time an O(1) operation?
with 0 being where my house is located, then to check for all the houses located at distance 1(Chebyshev distance) doesn't seem like an O(1) operation to me. Is there a better way to keep on expanding it in O(1) time?
Yes. You want to count how many houses are there in the expanded range.
One way is to use prefix sums. Vertical and horizontal prefix sums are enough to calculate the new square boundary in $$$O(1)$$$.
Another way is, well, also prefix sums :) Use 2D prefix sum to calculate how many houses in the entire 2-square, then subtract with how many houses in the 1-square. Still $$$O(1)$$$.
My solution:
Split the rectangle into 4 subrectangles, like that:
12
34
Now you have 10 variants for each pair of houses in which subrectangles they are:
-pairs 1-1, 2-2, 3-3, 4-4: solve recursively;
-pairs 1-4 and 2-3: any path that begins in 1 and ends in 4 goes through some center cell; so calculate for each distance how many houses in 1 and in 4 have this distace to this center cell and then multiply these two vectors by fft and add to answer; same for 2-3;
-pair 1-3: split it like that:
1.1 1.2
3.1 3.2
multiply by fft vectors of 1.1 and 3.2 and add to answer, same for 3.1-1.2, recursively go to 1.1-3.1 and 1.2-3.2; same for 2-4 and same for 1-2 and 3-4, but split horizontally.
btw, when the sizes of rectangles in recursion become <100 i stopped recursion and calculated distances manually
I thinks its better to stop at (.53 * sqrtlogn) iterations because it allows optimal bitset converging useful for fft.
But the main trick is to maintain of bitset.
Bitset works quite well. O(N^4 / 32) ~ 2.5 * 10^8 operations per test case.
Can you explain your solution?
For finding distances of ones between each row, we shift them and calculate bitwise and. Click for the code.
Let dp[row][col][dist] = number of vertices (_row, _col) such that _row ≤ row and the manhattan-distance from (row, col) to (_row, _col) equals dist.
Then, to calculate dp[row][col][dist] we can split it into two cases:
- we calculate the case when _row = row in O(n2).
- the answer for the case _row < row equals dp[row - 1][col][dist - 1], since to go from (row, col) to any other vertex above (row, col) we must go upwards at least once, thus landing on (row - 1, col).
PS: dp[row][col][dist] might exceed the memory limit I'm not sure(I'm back to cp after almost a year). But since we're only using dp[row - 1] to calculate dp[row], we can just keep one single dp[col][dist] and update it for each new row.
Actually, I too used the same approach and my solution passed for the given array size.
I knew that I was doing something wrong when I had to write this monster of a 200 line solution: Link. Glad to know that more elegant solutions exist.
BTW, you can go to the discuss.codechef.com to see the editorials and click on the appropriate tag for the contest.
Auto comment: topic has been updated by brdy (previous revision, new revision, compare).
O(n^3logn) solution worked, by applying binary search on each diagonal for every house.
I had TLE with O(n^3 log(n)), but you can easily change it to O(n^3) by just keeping track of two pointers, and that passed.
Can somebody tell if the complexity of this is O(T*N*M)?
Your 'v' is an O(n*m) vector.