PROBLEM LINK:
Author: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Yury Shilyaev
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic programming, cumulative sums.
PROBLEM:
You are given an N by M grid of characters ‘.’ and ‘#’. Path of player one is going from (1, 1) to (1, M), path of player two is going from (N, 1) to (N, M). Boths paths can consist of moves to the right, up or down of the grid, and only by ‘.’. You have to count number of pairs of paths.
QUICK EXPLANATION:
Imagine first player stays in (i, c) and second player stays in (j, c). Where they can be on column c + 1?
EXPLANATION:
Let i_{up} be number of row, where we will come, if we start from (i, c) by going directly up, while the second player is just staying in his row. i_{dw} the same, but we are going directly down. Let dp[c][i][j] be the number of pairs of paths, such that the first player did the move (i, c - 1) -> (i, c) and the second did the move (j, c - 1) -> (j, c).
If we consider only states where i < j, we can make a transition to dp[c + 1] by simply adding dp[c][i][j] on submatrix:
dp[c + 1][i'][j'] += dp[c][i][j] (i' \in [i_{up}, i_{dw}], j' \in [j_{up}, j_{dw}]).
Let’s precalculate first stone to the up and to the down of every cell to find i_{up} in O(1). Now, using cumulative sums we calculate dynamic programming in O(n^2 \cdot m) time. To achieve O(n^2) memory, we should calculate dp layer by layer, then we can reduce c parameter.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.