PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given a binary string S.
In one move, you can choose an index i such that S_i = 1, and set S_i = 0.
However, you cannot choose adjacent indices on consecutive moves.
Is it possible to make S have only zeros, using some sequence of moves?
EXPLANATION:
Let’s work out a few simple cases first.
The most trivial case is when S already contains only zeros - here, clearly the answer is Yes, and no moves are needed.
The second most trivial case is when S contains a single 1 - here again the answer is Yes, since there are no restrictions on our first move; meaning we can turn the sole 1 into a 0.
Next, consider the case when S contains two occurrences of 1.
There are two possibilities:
- Suppose the 1's are next to each other, i.e., S_i = S_{i+1} = 1 for some index i.
Here, the answer is clearlyNo, since after operating on one index we cannot operate on the other one. - Suppose the 1's are not next to each other.
Then the answer isYes, since operating on both ones is safe.
Next, we look at the case when S contains three occurrences of 1.
Here, it’s again easy to see that if all three ones are contiguous (i.e. S_i = S_{i+1} = S_{i+2} = 1 for some i) then the answer is No; and otherwise the answer is Yes.
Naturally, the next step is to look at when S contains four occurrences of 1.
Here, however, a bit of analysis shows that the answer turns out to always be Yes!
The construction is simple: if the ones appear at indices i_1, i_2, i_3, i_4 from left to right, we can simply use the ordering (i_2, i_4, i_1, i_3).
It’s easy to see that a similar idea works for all larger counts too.
That is, if the ones appear at positions i_1, i_2, \ldots, i_k from left to right, where k \ge 4, then we can always operate on all of them by following the order
i_2, i_4, i_6, \ldots, i_1, i_3, i_5, \ldots
That is, operate on all even-numbered ones from left to right; then all odd-numbered ones from left to right.
From what we’ve done above, we can see that the answer is almost always Yes.
There are only two exceptional cases:
- S contains two occurrences of 1, and these occurrences are consecutive.
That is, S looks like 00\ldots 001100\ldots 00 - S contains three occurrences of 1, and these occurrences are consecutive.
That is, S looks like 00\ldots 0011100\ldots 00
Both cases are easy to check in linear time; so we’re able to easily answer Yes or No.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
l, r = 0, n-1
while l < n:
if s[l] == '1': break
l += 1
while r >= 0:
if s[r] == '1': break
r -= 1
if l+1 == r or l+2 == r and s[l+1] == '1':
print('No')
else:
print('Yes')