P4_175 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: fireheart17
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

simple

PREREQUISITES:

None

PROBLEM:

You have a binary string S. You can perform the following operations on it, alternatingly:

  1. Rearrange some substring of S however you like.
  2. Convert some substring of S to its complement.

Find the minimum number of operations needed to make S an alternating string.

EXPLANATION:

First, note that for a string to be alternating, it should have an (almost) equal number of zeros and ones.
Specifically, the difference between the count of zeros and the count of ones should be at most 1.

Being able to rearrange a substring of S however we like is a very powerful operation - note that you can always just choose the entirety of S to rearrange here.
In fact, it allows us to always be able to form an alternating string using three operations:

  1. In the first operation, sort S, so that all zeros come before all ones.
  2. In the second operation, suppose there are more ones than zeros. Convert some of the ones to zeros (by choosing a substring of ones - note that they’re all together now), such that the resulting string has |\text{count}(0) - \text{count}(1)| \leq 1.
  3. Now that the counts differ by at most 1, in the third operation rearrange the string to be alternating.

This means we only need to check whether using fewer than three moves is possible.
Let’s look at each of them separately.

Using 0 moves is trivial to check: the string must already be alternating.

Using 1 move is also easy to check, since we can only rearrange the string.
In fact, we’ve already seen how: if |\text{count}(0) - \text{count}(1)| \leq 1 then the string can be rearranged into an alternating one; otherwise it cannot.

This leaves checking for \text{answer} = 2 as the only non-trivial case.
Now, we can rearrange the string once, then take the complement of some substring, and then the resulting string must be alternating.

Let’s forget the initial rearrangement for now, we’ll come back to it.
Suppose our second move is to convert substring S$[L, R]$ to its complement, after which the resulting string becomes alternating.
Then,

  • S[1, L-1] and S[R+1, N] must have already been alternating.
  • S[L, R] must also have been alternating initially.
  • If L\gt 1, S_L = S_{L-1} must hold before the operation, so that they’re unequal after it.
  • Similarly, if R\lt N then S_R = S_{R+1} must hold before the operation.

Note that the first two conditions here are quite strong: they tell us that S can be broken up into three alternating substrings; so from the earlier discussion we know that each of these parts must have |\text{count}(1) - \text{count}(0)|\leq 1.
This means, for the entire string, we must have |\text{count}(1) - \text{count}(0)|\leq 3.

So, immediately if |\text{count}(1) - \text{count}(0)|\gt 3 we can say that using two moves cannot be enough, and the answer must thus be three.
What about when |\text{count}(1) - \text{count}(0)|\leq 1?

Well, if the difference is \leq 1 we already saw that the answer is 1, so we only have to deal with difference 2 and 3.
In both cases, it turns out that it’s possible to use two operations to make the string alternating, so we’re done!

Proof

Suppose the difference is 2, without loss of generality let \text{count}(0) = \text{count}(1) + 2.
Then, in the first operation the string can be arranged to be

101010\ldots101000

That is, alternating ones and zeros (starting with a 1) till all ones are used up; then place the extra two zeros.
In the second operation, simply choose the second-last zero and flip it to a 1, which makes the string alternating.

Next, suppose the difference is 3, and again let \text{count}(0) = \text{count}(1) + 3.
Rearrange the string to

010101\ldots01000

That is, make an alternating string starting with 0 till all the ones are used up, and then place the extra three zeros at the end.
Then, just as before, flip the second-last zero to a 1 and the string becomes alternating.

In summary:

  • If S is already alternating, the answer is 0.
  • Otherwise, if |\text{count}(1) - \text{count}(0)|\leq 1 the answer is 1.
  • Otherwise, if |\text{count}(1) - \text{count}(0)|\leq 3 the answer is 2.
  • If all three checks fail, the answer is 3.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
def solve(s):
	# Check for alternating
    if len(s) == 1 or (min(s[::2]) == max(s[::2]) and min(s[1::2]) == max(s[1::2]) and s[0] != s[1]):
        return 0
    
    zero, one = s.count('0'), s.count('1')
    
    if abs(zero - one) <= 1:
        return 1
    
    if abs(zero - one) <= 3:
        return 2
    
    return 3

for _ in range(int(input())):
    s = input().strip()
    print(solve(s))
2 Likes