How to solve AVGMAT?

Правка en1, от brdy, 2018-10-22 19:15:44

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?

Теги #dp, #codechef, #oleg, #bitset

История

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