PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
You’re given a binary array A.
Construct an N\times N grid B such that B_{i, j} = \sum_{k = \min(i, j)}^{\max(i, j)} A_k.
Let M be the minimum cost of a right-down path from (1, 1) to (N, N) in this grid.
Find the number of paths whose cost is M.
EXPLANATION:
We already know from the easy version that the minimum cost equals
This is achieved by starting with the subarray [1, 1] and moving its borders one step at a time (while ensuring the subarray is non-empty), till [N, N] is reached.
The specific greedy strategy we used was to move from (i, i) to (i, i+1) and from (i, i+1) to (i+1, i+1) always.
Now, we need to count the number of paths that attain the minimum - so we need to understand the structure of such paths a bit more.
Recall that each index must be included three times at minimum in the subarrays along our path - except for the borders which must be included twice instead.
Since each A_i is either 0 or 1, the only real restriction set upon us, is given by those indices with A_i = 1.
As long as we ensure that all these indices are visited exactly three times each (two for the borders), the cost will remain minimal - no matter how many times the indices containing zeros are visited.
Let’s now understand which sorts of paths visit some index exactly three times.
So, consider some index i; for simplicity we assume 1 \lt i \lt N now (the borders can be handled similarly).
Let [L, i] be the first time a subarray includes index i.
Now, if L \leq i-2, we will surely include index i at least four times: the quickest possible way to leave i is the sequence [L, i] \to [L+1, i] \to \ldots \to [i-1, i] \to [i, i] \to [i, i+1] \to [i+1, i+1], which has length \ge 4 when L \le i-2.
So, if we are to include i only three times, we must have L = i-1, i.e. visit it with the subarray [i-1, i] for the first time; meaning the subarray was [i-1, i-1] earlier.
Further, it can be seen that there are exactly six ways to include index i three times:
- [i-1, i-1] \to [i-1, i] \to [i, i] \to [i, i+1] \to [i+1, i+1].
This can be done in four ways: the two moves for [i-1, i-1] \to [i, i] can be done in either the upper or lower triangle, and similarly the two moves for [i, i] \to [i+1, i+1] can be done in either triangle; both are independent so they can be multiplied. - [i-1, i-1] \to [i-1, i] \to [i-1, i+1] \to [i, i+1] \to [i+1, i+1].
This can also be done in either the upper or lower triangle, for two ways.
Note that this move results in i-1 and i+1 both being visited \ge 4 times each (if you also include previous/following moves), so this is only valid when A_{i-1} = A_{i+1} = 0, and cannot be done otherwise.
This brings up one more property that’s quite useful: along our path, we’ll visit cells of the form (i, i), i.e. the diagonal of the grid, quite often; in fact, if A_i = 1, then we’re forced to visit both (i-1, i-1) and (i+1, i+1).
Further, we start on the diagonal and need to end on the diagonal.
This observation lends itself to a solution using dynamic programming.
Let dp_i denote the number of minimal paths starting at (1, 1) and ending at (i, i).
Using earlier observations, this ends up being not too hard to compute.
Case 1: A_i = 1.
Here, we know for a fact that any minimal path must visit (i-1, i-1).
Once there, there are two ways for it to reach (i, i), both of which are valid.
So, we simply obtain dp_i = dp_{i-1} \cdot 2 for this case.
Case 2: A_i = 0.
There are two possibilities here: either A_{i-1} = 1, or A_{i-1} = 0.
Case 2.1: A_{i-1} = 0.
Let p \lt i be the largest index such that A_p = 1; choose p = 0 if no such index exists.
We then know that any valid path must visit (p+1, p+1).
Once at (p+1, p+1), everything upto i is just zeros - which means any path from (p+1, p+1) to (i, i) is valid.
The number of such paths is exactly \binom{2i - 2p - 2}{i - p - 1}, because we need to make (i - p - 1) each of right and down moves, and this can be done in any order.
So, here we obtain dp_i = dp_{p+1} \cdot \binom{2i - 2p - 2}{i - p - 1}.
Case 2.2: A_{i-1} = 1.
Here, we know that any valid path must visit (i-2, i-2) for sure.
From there, there are four ways to get to (i, i) via (i-1, i-1), all of which are valid.
Further, if A_{i-2} = 0, there are an additional two ways that don’t pass through (i, i).
So, depending on whether A_{i-2} = 0 or not, we obtain dp_{i-2}\cdot 6 or dp_{i-2}\cdot 4 as the value of dp_i.
Each dp_i can thus be computed in constant time; after which the answer is simply dp_N.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
mod = 998244353
N = 2*10**6 + 10
C = [1]*N # 2n choose n
for i in range(1, N): C[i] = C[i-1] * (4 - 2 * pow(i, mod-2, mod)) % mod
for _ in range(int(input())):
n = int(input())
a = '1' + input()
dp = [1]*(n+1)
prv1 = 0 if a[1] == '0' else 1
for i in range(2, n+1):
if a[i] == '1':
dp[i] = 2*dp[i-1] % mod
prv1 = i
elif a[i-1] == '1':
dp[i] = 2*dp[i-1] % mod
if a[i-2] == '0': dp[i] = (dp[i] + 2*dp[i-2]) % mod
else:
dp[i] = dp[prv1+1] * C[i-prv1-1] % mod
print(dp[n])