In the recent snackdown round A qualifier, there was a problem I could not figure out.
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?