INVEQ - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sky_nik
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given a binary string S. In one move, you can choose a substring consisting of all equal characters, and flip it.
Find the minimum number of moves needed to make all the characters of S equal.

EXPLANATION:

S is a binary string, so it can be broken up into several contiguous maximal ‘blocks’ of equal characters.
For example, S = \texttt{10010110110111} breaks up into \{\texttt{1, 00, 1, 0, 11, 0, 11, 0, 111}\}.
Looking at the string in terms of blocks like this is useful here, since we must always choose some substring of equal characters (meaning it should be fully contained within some block).

Suppose there are x blocks of zeros and y blocks of ones.
To turn every character into 0, clearly one way is to choose an entire block of ones in one move and flip it. This way, you need y moves.
Similarly, every character can be turned into 1 using x moves.
So, it’s definitely possible to make all the characters equal using \min(x, y) moves.

This is also optimal.

Why?

One way to look at the number of blocks in a binary string is: 1, plus the number of indices i such that S_i \neq S_{i+1}.
That is, the first block, along with the number of times the block changes from 0 to 1.

Now, suppose you flip the substring from l to r. Observe that:

  • If l \gt 1 and S_l = S_{l-1}, the number of blocks will increase by 1.
  • If l \gt 1 and S_l \neq S_{l-1}, the number of blocks will decrease by 1.
  • Similarly, if r\lt N then the number of blocks will either increase or decrease by 1 depending on whether S_r = S_{r+1} or not.
  • These are the only changes in the number of blocks.

Our final aim is to bring the number of blocks down to 1, which is when all the characters are equal.
From above, we can see that in one move, the number of blocks can be decreased by at most 2 in a single move.
So, if there are B blocks, we definitely need at least \left\lfloor\frac{B}{2}\right\rfloor moves to bring the count down to 1.
This is exactly what \min(x, y) is!

The last statement follows from the fact that zeros and ones alternate blocks, so we have |x-y| \leq 1.
Along with x+y=B, it can be seen that both x and y have to be half of B; when B is even they’ll be equal and when B is odd the smaller one will be the floor of half of B.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ct = 0
    for i in range(n-1):
        ct += s[i] != s[i+1]
    print((ct+1)//2)
1 Like