DIREP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Dynamic programming

PROBLEM:

You have a binary string S.
You can do the following operation on it:

  • Choose a substring that equals 1010 and turn it into 1100, or
  • Choose a substring that equals 0101 and turn it into 0011.

EXPLANATION:

We’ll say that the operation is performed on index i, if the substring S[i:i+3] is updated.

Suppose we have S_i = S_{i+1} for some index i.
Then, observe that no operation can ever change the values at these indices.
This is because, if an element is changed by the operation, it has to be among the middle two of four elements for which each adjacent pair is different.
However, for S_i to be in the middle we’ll have to include S_{i+1} and they aren’t different from each other; so there’s no way to change it.

In particular, note that this means if we ever perform an operation on index j, it can’t include both i and i+1: meaning either j+3 \leq i or j \geq i+1.

Next, suppose we perform the operation on index i.
This will then result in S_i = S_{i+1} and S_{i+2} = S_{i+3}, so by our previous observation, none of these four indices can ever change again.
This means that the part of the string till i is now completely independent of the part of the string after i+3.

This allows us to formulate the following dynamic programming solution.
Let dp_i denote the number of distinct strings that can be formed, when only considering the first i elements of S.

Then,

  1. We always have dp_{i-1} possibilities, by just working with the first i-1 characters and ignoring the last one.
  2. There is however one more option: we can operate on index i-3 (so the substring S[i-3:i]) if it’s valid to do so.
    If we do this, then the values of S_{i-1} and S_{i-2} will change, and as noted earlier, all future operations can’t touch these anymore.
    This means we’ve essentially cut out the last three characters - so there are dp_{i-3} options for what to do with the remaining.

Quite simply:

  • dp_i = dp_{i-1} + dp_{i-3} if S[i-3:i] equals either 1010 or 0101.
  • dp_i = dp_{i-1} otherwise.

The answer is dp_N.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
for _ in range(int(input())):
    n = int(input())
    s = input()
    dp = [0]*n
    dp[0] = 1
    for i in range(1, n):
        dp[i] = dp[i-1]
        if i >= 3:
            if s[i-3:i+1] in ['1010', '0101']: dp[i] += dp[i-3]
        dp[i] %= mod
    print(dp[n-1])
1 Like