BINFLIP - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

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

x=\frac{K\oplus (2^{\lfloor\log_2 K\rfloor+1}-1)}{2}
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:

O(\log_2(K))

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

2

Can you please help me figure out… why my code gives WA?
@infinitepro

https://www.codechef.com/viewsolution/52960690

3

My solution was a bit different, although I am too going from highest power to lower power.
Firstly, I will describe how I made the observation of answer being YES for every odd number.
I wrote a recursive DP solution to check if combination N, K is valid, this was of complexity 2^N, although this is not being used in final solution but this helped me observe that answer was YES for every odd number. Link to this recursive DP function to check if N, K is valid: DP recursive check for Snackdown R1A BINFLIP · GitHub

Now after I ran this on numbers form 1-100 I observed that it was YES for odd, then I did some dry runs for odd numbers on pen and paper and observed that if I apply flip operations from highest power from start index of 1’s segment or ending at end index of 1’s segment in case we exceed N, then we can arrive at solution.
So I maintained start and end index for 1’st segment and just updated these values on each operation, if any operation goes out of bounds of N then I just applied that operation at end of 1’s segment instead.
Link to solution: CodeChef: Practical coding for everyone

3 Likes
4

I wrote a recursive DP solution to check if combination N, K is valid, this was of complexity 2^N, although this is not being used in final solution but this helped me observe that answer was YES for every odd number.

I wrote a super trivial naive bruteforcer, which worked only up to K=17. That’s kinda very small, but still allowed me to successfully make the odd numbers observation and generate small random testcases for validating correctness of a more sophisticated solution. I actually think that this made solving problem BINFLIP much easier than EQBEAUTY (implementing a correct bruteforcer for EQBEAUTY’s small input was more tricky due to handling some corner cases).

2 Likes
5

Exactly, I solved BINFLIP long before I solved EQBEAUTY.

6

I think there’s a mistake in the tester’s output. Because all of the edge cases work perfectly for my code.

Do mention the edge case if I’m wrong.

https://www.codechef.com/viewsolution/52960690

7

Try the following testcase:

1
5 5

Your code says NO, but one of the possible correct answers is:

YES
3
4
4
1
1 Like
8

Can any one please tell me which test am i missing
https://www.codechef.com/viewsolution/52879554

9

Your solution is awesome!
Here is a shorter and clearer code: CodeChef: Practical coding for everyone

1 Like
10

Check the comment right above yours. Your code is failing exactly the same N=5 K=5 testcase.

11

Thanks , i got it now

12

1
10 9

13

I had question can you tell me what will be output for
1
15 13

14

The answer is YES for any odd K. The value of N doesn’t matter and any correct solution for N=13 K=13 will be also correct for your N=15 K=13 case. Also there is more than one way to construct a correct output, so different correct solutions may produce different output. If N=15 K=13, then my solution prints

YES
4
8
8
10
1

And the solution of @zeus2198 prints

YES
4
14
13
9
1

Both of them are correct. If you are interested, I can explain my way of constructing the output.

15

bro plz help me i did’t found where i got wrong
// author → vivek parashar
// stamp → 21-10-21

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main() {
// your code goes here
ll t;
cin>>t;

while(t--)
{
    ll n, k;
    cin>>n>>k;
    
    if(k==0) cout<<"YES\n0\n";
    else if(k==1) cout<<"YES\n1\n";
    
    else if(((k+1) & k) == 0 )
    {
        cout<<"YES\n";
        cout<<(int(log2(k+1)))<<"\n";
        
        k+=1;
        int count=0;
        
        while(k>1)
        {
            k-=pow(2, count);
            cout<<k<<"\n";
            count++;
        }
    }
    else cout<<"NO\n";
}
return 0;

}

16

you can get answer by using only first k characters irrespective of the value of n!!
your solution seems to depend on the value of n…try using test case :
2
10 9
15 9
your code gives two different verdicts… correct answer should be :
YES
4
8
6
6
1

17

For n=11 and k=11
Is the following output correct ?

YES
4
11
8
2
1
18

No, this output is incorrect. My simple validator script says “Error: the end result is not zero (0111100101) for N=11 K=11”.

19

The formatting of the code in your comment is broken. Could you please edit your comment to fix formatting? Or even better, just replace the pasted code by a link to your submission.

20

but according to question the first k value of n is 1
“CodeChef: Practical coding for everyone”