COPYCAT - Editorial

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a binary string.
You can choose an index i (1 \le i \lt N) and set S_i to S_{i+1}.
Find the minimum operations needed to sort S.

EXPLANATION:

A sorted binary string looks like several zeros followed by several ones.
Also note that our operation does not allow us to change the last character of S.

So, in particular if S_N = 0, our only choice for a sorted final string is to have all zeros.
This requires one operation for each 1 in the string, which is always attainable (choose the rightmost occurrence of 1, it must have a 0 to its immediate right so it can be overwritten.)
So in this case the answer is simply the count of ones in S.


From now, we assume S_N = 1.
Suppose we want the final sorted string to have k zeros followed by N-k ones.
How many operations are needed to achieve this?

Well,

  • The first k characters must be 0. Each operation can overwrite only one index, so certainly every 1 in this prefix needs one operation each.
  • Similarly, the last k characters must be 1, so we need one operation for each 0 in the suffix.

Observe that as long as S_k = 0, we can use exactly these many operations; utilizing the same idea as what we did when S_N = 0 above:

  • Repeatedly pick the righmost 1 in [1, k], it must have a 0 to its right so overwrite it.
  • Repeatedly pick the rightmost 0 in [k+1, N], it must have a 1 to its right (recall that we’re in the case where S_N = 1) so overwrite it.

What if S_k \ne 0 however?
We don’t need to even consider such a k, since it will never be optimal!
This is because, if S_k \ne 0, then the answer for k-1 can never be higher than the answer for k; because looking at k-1 we have one fewer 1 in the prefix and the same number of zeros in the suffix.

So, when S_N = 1, the answer is simply the minimum of (ones in the prefix of length k) + (zeros in the suffix of length N-k), across all 0 \le k \le N.

This can be easily implemented in \mathcal{O}(N^2) which is fast enough for the given constraints.
Linear-time solutions are also possible, if you wish to implement them.

TIME COMPLEXITY:

\mathcal{O}(N^2) or \mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3)
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    if s[-1] == '0': print(s.count('1'))
    else:
        ans = n
        for i in range(n+1):
            ans = min(ans, s[:i].count('1') + s[i:].count('0'))
        print(ans)
1 Like