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