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