BSHORT - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a binary string S of length N.
You can choose one of its substrings - then if that substring has an odd number of ones, delete all zeros in it; otherwise delete all ones in it.

Find the minimum possible length of the final string.

EXPLANATION:

If you play around with the operation a bit, you can make the following observations:

  • If there are no 1's in the string, nothing more can be done.
  • If there’s at least one 1 in the string, every 0 in the string can be deleted.
    This is because, if the string contains both a 1 and a 0, it must also contain one of the the substrings 01 or 10.
    Operating on this substring will delete the 0 from it; which can be repeated till no more zeros remain.

Now, suppose there’s at least one 1 in the string - so we can delete all the zeros from S using the strategy above.
We now have a string that’s all ones.

If there are an even number of ones, simply choosing them all will delete all of them, leading to a length of 0 - clearly this is optimal.

If there are an odd number of ones, we can choose all of them other than the first - and that’s an even number, so they’ll all be deleted.
That leaves a single 1 remaining.
It turns out that this is optimal too - notice that whenever you delete ones from S, an even number of them get deleted; so if you start out with an odd number of ones, you will end up with an odd number of ones too (in particular, you cannot have 0 ones in the end).

This gives us a fairly simple solution:

  1. If S doesn’t contain any ones initially, the answer is N.
  2. Otherwise, let c denote the number of ones in S.
    • If c is even, the answer is 0.
    • Otherwise, the answer is 1.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()

    ones = s.count('1')
    if ones == 0: print(n)
    else: print(ones % 2)
1 Like