How to solve AVGMAT?

Revision en1, by 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?

Tags #dp, #codechef, #oleg, #bitset

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English brdy 2018-10-23 00:30:29 577
en1 English brdy 2018-10-22 19:15:44 760 Initial revision (published)