PROBLEM LINK:
DIFFICULTY:
MEDIUM
PROBLEM:
Given a binary string S of length N, where the first K characters are 1 and the rest are 0. You want to make all characters 0, by applying the following operations at most \log_2(N)+1 times.
- In the i^{th} operation, you may select any 2^{i-1} length substring of S and flip the values.
Determine if it is possible to do this (along with a sequence of operations to achieve the same).
EXPLANATION:
Let’s do away with the trivial case where K=0, where no operations are needed to make all characters 0. Now, we only consider K>0.
Claim: If K is an even integer, then it is impossible to make all characters 0.
Proof
It is easy to see that the 1^{st} operation changes the number of 1's in S by an odd count. It isn’t hard to similarly deduce that all subsequent operations i\ (i>1) changes the number of 1's in S by an even count (why?)
Therefore, applying the first i operations on S changes the number of 1's by an odd count. But K is even, and so we want to change the number of 1's in S by an even count, which is impossible.
Thus proved.
When K is odd, I claim it is always possible, irrespective of the value of N. More precisely, we require at most \log_2(K)+1 operations, each applied only on some substring of S[1..K] (which is equivalent to saying that the last N-K characters of S are never flipped).
The rest of the solution is constructive.
Hint 1
Try working backwards.
You have a binary string of length K (we ignore the last N-K characters, since I claimed above that it isn’t necessary to flip them ever), initially all 0.
Apply the operations on it in reverse order (operation log_2(K)+1, followed by operation log_2(K) and so on) to make the string all 1.
Trial and error is your best friend.
Hint 2
Look at the binary representation of K. What would your sequence of operations be, when K (in base 2) is equal to:
- 1111
- 1101
- 1001
Hint 3
I claim that it takes at most one operation that flips a segment of 1's. In other words, there exists a solution such that all but one operations flip a substring consisting only of 0's.
Solution
Let’s work the solution backwards. We have a binary string S of length K, all characters initially 0. We apply operations in reverse order, from operation log_2(K)+1 to operation 1. Our goal is to make all characters of S equal 1.
Watch out for the EXAMPLE spoilers throughout the rest of the section, that’ll visualise how the solution is applied in steps to a particular test case.
EXAMPLE
Let’s generalise the construction through an example. Say K = 51 = (110011)_2. We then have to flip substrings of length 2^5,2^4,2^3,2^2,2^1,2^0, in that order.
STEP 1: Let 2^i be the length of the substring that we are currently considering to flip. If the i^{th} bit of K is set, flip the leftmost substring of S consisting of only 0's. If not set, goto step 2. Do this iteratively for each i.
EXAMPLE
Looking at our example, we do this step for i=5 and i=4, before moving on to step two. The string S transforms in the following fashion:
000000000000000000000000000000000000000000000000000 // Initial
111111111111111111111111111111110000000000000000000 // 32 ones
111111111111111111111111111111111111111111111111000 // 16 more
STEP 2: Flip a substring of length 2^i such that, the total number of 0's in S after this operation is equal to 2^i-1. A little mathematical manipulation guides us to flip the x rightmost 1's (and the 2^i-x leftmost 0's), where
How did you conjure this?
EXAMPLE
Continuing with our example, we calculate x=6. Then the string after applying step two to S is given below.
111111111111111111111111111111111111111111000000110
STEP 3: Let S_1 and S_2 be references to the two separated substrings of S that are composed of only 0's (S_2=``" if it doesn’t exist). For all subsequent operations of length 2^i, flip the leftmost, 0-filled substring (of length 2^i) of string
- S_1, if the i^{th} bit of |S_1| is set, and
- S_2, otherwise.
Reasoning
|S_1|+|S_2| = 2^x-1 (where substring of length 2^x was flipped in step two), and we can flip a total of 2^{x-1}+2^{x-2}+\dots+2^0=2^x-1 characters over all subsequent operations.
So flipping non-overlapping segments in each move, using the bitwise representation of the lengths of the two strings to guide us is a viable idea.
EXAMPLE
Completing our example, S is transformed in the following fashion:
111111111111111111111111111111111111111111000000110 // End of step two
111111111111111111111111111111111111111111111100110 // 4 flips
111111111111111111111111111111111111111111111111110 // 2 flips
111111111111111111111111111111111111111111111111111 // 1 flips
Now, doing the same operations in reverse on the original string S (as given in the problem) gives a valid solution to the actual problem!
TIME COMPLEXITY:
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters