DISPART - 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:

Easy

PREREQUISITES:

None

PROBLEM:

A witness for a binary string B is an integer X in [1, N] that satisfies the following:

  • Let S_1 be the array consisting of i \ \& \ X for all i such that B_i = 0.
  • Let S_2 be the array consisting of i \mid X for all i such that B_i = 1.
  • S_1 \cap S_2 = \emptyset should hold.

Given a binary string of length N, find the minimum number of single-index flips needed to turn it into a string with no witnesses in [1, N], or claim that this is impossible.

EXPLANATION:

Let’s understand when some X is not a witness for a binary string A.
This happens when, after computing the arrays S_1 and S_2, we have S_1 \cap S_2 \neq \emptyset.
In particular, this means there must exist indices i, j such that:

  • A_i = 0
  • A_j = 1
  • i \ \& \ X = j \mid X

Now, note that i \ \& \ X \leq X, since the bitwise AND of X with something else will only contain some of the bits of X, and definitely can’t contain anything else.
On the other hand, j\mid X \geq X, because the bitwise OR of X with something else will contain all the bits of X, along with maybe some others.

This means that i \ \& \ X = j \mid X is only possible when i \ \& \ X = j \mid X = X.

Observe that i \ \& \ X = X happens if and only if i is a supermask of X, i.e. every bit set in X is set in i.
Similarly, j\mid X = X happens if and only if j is a submask of X.

Let’s relate the above observations to our goal.

We want a binary string with no witnesses: meaning, for every X \in [1, N], we must have:

  • Some submask j of X for which A_j = 1, and
  • Some supermask i of X for which A_i = 0.

Let’s look at the first condition for now.
Suppose X = 2^k is a power of 2.
The only submasks of X are then 0 and X itself.
0 isn’t available to us, so to satisfy the condition of “there must exist a submask X which has B_j = 1”, we’re forced to set A_X = 1 itself.

Similarly, let’s look at the other extreme: suppose X is some element such that there’s no supermask of X in [1, N] other than X itself.
For such X, we’re forced to set A_X = 0 to satisfy the second condition.

Finding such X is not too hard: X has no supermask in [1, N] if and only if X + 2^b \gt N, where b is the smallest power of 2 not set in X.
This allows us to test each element in [1, N] for this condition quite easily.

We now have a set of indices whose values in A are fixed, either to 0 or 1.
Let’s compute the necessary changes that must be made to achieve this.

It turns out that these changes are also sufficient!

To see why, look at some any integer X in [1, N].

  • Let Y be the largest supermask of X present in [1, N].
    Note that Y then cannot have any supermask in [1, N] other than itself (since this would also be a supermask for X, contradicting Y being X's largest supermask).
    By construction, we’ve hence set A_Y = 0, so X does have a supermask with value 0.
  • All the powers of 2 have value 1, so X also has some submask with value 1 (take any bit set in its binary representation).
  • So, X is surely not a witness for this string A, as we wanted.

The only time our solution can fail, is if some element is forced to be set to both 0 and 1, by virtue of both being a power of 2 and not having a supermask larger than itself.
This is only possible when N = 2^k for some k, i.e. N is a power of 2.
In every other case, 2^k+1 is a supermask of 2^k when k \ge 1, and 3 is a supermask of 2^0 = 1.

So, for N = 2^k alone no solution exists, while for everything else the solution is to set all powers of 2 to value 1, and all X without larger supermasks to value 0.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = '0' + input()
    
    if n & (n-1):
        ans = 0
        for i in range(1, n+1):
            if i & (i-1):
                small = 0
                for b in range(20):
                    if (i >> b) & 1: continue
                    if i + (1 << b) <= n: small = 1
                if not small: ans += a[i] == '1'
            else:
                ans += a[i] == '0'
        print(ans)
    else:
        print(-1)