How to solve AVGMAT?
Разница между en1 и en2, 577 символ(ов) изменены
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 .-.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский brdy 2018-10-23 00:30:29 577
en1 Английский brdy 2018-10-22 19:15:44 760 Initial revision (published)