MXON - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: hellolad
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given a binary string S. In one move, you can set S_i := \max(S_i, S_{i+1}).
This can be done at most K times.
Find the maximum possible number of ones in S.

EXPLANATION:

Since we’re dealing with a binary string, \max(S_i, S_{i+1}) can only be either 0 or 1.
In particular,

  • If S_i = 1, then \max(S_i, S_{i+1}) = 1 always, and S_i won’t change.
  • If S_i = S_{i+1} = 0, \max(S_i, S_{i+1}) = 0 and so S_i won’t change again.
  • So, the only way S_i can change is if S_i = 0 and S_{i+1} = 1, in which case S_i becomes 1.

Essentially, our only ‘useful’ move is to take some 1 and convert a 0 to its left into a 1.

Let R be the rightmost index containing a 1 in S.
Every element after R will be a 0, and as seen above we can’t change them anyway, so we can essentially ignore everything after R entirely.
As for the indices before R: suppose there are Z zeros among them. In each move we can convert one of these zeros to a one (and it’s always possible to convert a 0 to a 1, for example by choosing the rightmost remaining zero before R).
So, using K moves, we can convert at most \min(Z, K) zeros to ones.
This added to the initial number of ones will give us the answer.

In summary, the solution is as follows:

  • Let R be the rightmost index containing a 1 in S.
    • If no such index exists, the answer is 0 since it means the string contains only zeros.
  • Let Z denote the number of zeros before R.
  • The answer is then \min(K, Z), plus the number of ones initially in S.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    last_one = s[::-1].find('1') # The last 1 in s is the first 1 in reverse(s)
    if last_one == -1: print(0)
    else:
        last_one = n-1-last_one # Convert to index in the original string
        zeros_before = s[:last_one].count('0')
        print(s.count('1') + min(k, zeros_before))