MARKP - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N points, initially all unmarked.
In one move, you can choose a location X (1 \lt X \lt N) and mark the three points X-1, X, X+1. Previously marked points stay marked.

Given a binary string S, does there exist a way to mark points such that point i is marked if and only if S_i = 1?

EXPLANATION:

In terms of the binary string S, what we can do is effectively: start with a binary string with all zeros, and then in each operation, set three consecutive elements of S to 1.

Since we can only set three consecutive elements to 1, observe that S can never contain a block of ones of length 1 or 2, i.e. it cannot contain \ldots 010 \ldots or \ldots 0110 \ldots (or start with 10\ldots and so on.)

As long as this condition is satisfied, it’s always possible to reach the target string.
A simple way of doing this is: consider a contiguous block of ones, from index L to index R (where R-L+1 \geq 3, so the block has length \ge 3).
Perform operations by choosing the indices L+1, L+2, \ldots, R-1 in order, and it will result in exactly all these indices obtaining the value 1 while not changing any other indices.
Repeat this for each block of ones to obtain the final string.

So, quite simply, the answer is "Yes" if every maximal contiguous block of ones in S has length \geq 3, and "No" otherwise.
This is easy to check: just compute all blocks of ones and see if their lengths are \ge 3.
Computing all blocks of ones can be done in linear time, though the constraints are small enough that implementations in \mathcal{O}(N^2) or \mathcal{O}(N^3) will work too.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = 'Yes'
    p = 0
    for i in range(n):
        if s[i] == s[p]: continue
        if s[i] == '0' and i <= p+2: ans = 'No'
        p = i
    if s[-1] == '1' and p >= n-2: ans = 'No'
    print(ans)