P4BAR - Editorial

editorial
, ,
1

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 operation, you can flip any one character from 0 to 1 or vice versa.
Find the minimum number of operations needed to make c_{11} \ge c_{00}, where c_{t} is the count of substring t.

EXPLANATION:

Let’s analyze how a flip changes the counts c_{00} and c_{11}.

So, suppose we flip the character at index i.
Then, we need to look at substrings of length two that can change; meaning we care about the characters adjacent to S_i.
Looking at possible cases, we find the following:

  1. Suppose S_{i-1} = S_{i+1} = 0.
    Then, depending on whether S_i = 0 before the flip or not, c_{00} will either increase by 2 or decrease by 2.
    c_{11} does not change at all.
  2. Suppose S_{i-1} = S_{i+1} = 1.
    This is similar to the first case, just that 11 and 00 switch roles - that is, c_{00} doesn’t change at all, while c_{11} either increases or decreases by 2.
  3. Suppose S_{i-1} \ne S_{i+1}.
    Then, either c_{00} will increase by 1 and c_{11} will decrease by 1, or vice versa.

Importantly, observe that in all three cases, the difference (c_{11} - c_{00}) will always change by either +2 or -2.

One thing to note here is that we assumed that S_{i-1} and S_{i+1} both exist - which means i is neither 1 nor N.
For i = 1 and i = N, the change is \pm 1 instead of \pm 2.

Now, our goal is to make c_{11} \ge c_{00}, which in turn means c_{11} - c_{00} \ge 0.

If this condition holds for the initial string, then of course no moves are needed and the answer is 0.
That leaves the case of when c_{11} - c_{00} \lt 0 initially.

As noted above, this difference can only be changed by +2 or -2 in a single move (endpoints aside).
Since our aim is to minimize the number of moves made, it’s clearly optimal to always have the change be +2.

It’s not hard to see that as long as c_{11} - c_{00} \lt 0, it’s always possible to increase the difference by 2 - a simple construction is to note that c_{11} - c_{00} \lt 0 means that there must exist some occurrence of 00 as a substring; so choose any such occurrence, and then one of its elements will be a non-endpoint so flipping that will give us what we want.
(Technically, N = 2 is an exception here; but it works out nonetheless since the answer would be 1 in that case.)

Thus, the number of moves is simple: it’s just the number of times we need to add 2 to the initial value of (c_{11} - c_{00}) to make this difference become \ge 0.
This is simply \displaystyle\left\lceil \frac{c_{00} - c_{11}}{2} \right\rceil, where \left\lceil x \right\rceil denotes the result of rounding x up to the nearest integer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    c00, c11 = 0, 0
    for i in range(n-1):
        if s[i] == '0' and s[i+1] == '0': c00 += 1
        if s[i] == '1' and s[i+1] == '1': c11 += 1
    
    if c11 >= c00: print(0)
    else: print((c00 - c11 + 1) // 2)