CHEFLAKE - Editorial

cook94
dynamic-programming
prefix-sum

#1

PROBLEM LINK:

Practice
Contest

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]*[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]*[j] on submatrix:

dp[c + 1][i'][j'] += dp[c]*[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.


#2

Can anyone share the top-down approach code? I implemented it using top down DP using FloodFill technique but could not properly think how to restore back array because it gets changed after implementing one of the three possible paths from a given point.


#3

Tester’s solution redirecting back to this page. Fix the link.


#4

A top-down approach will not work here because you will not be able to apply the 2D prefix sum optimization.


#5

thanks ! That cleared my doubt.Was thinking of the same.