BINFLIP - Editorial

editorial
, ,
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”

21 
#include <stdio.h>

int main(void) {
	int t,n,k,i,j,a;
    scanf("%d",&t);
    for(i=0;i<t;i++){
        scanf("%d %d",&n,&k);
        if(k==0){
            printf("YES\n0\n");
        }else{
            a=0;
            for(j=1;j<n;j++){
                if(pow(2,j)-1 == k){
                    printf("YES\n%d\n",j);
                    a=j;
                }
            }
            if(a == 0){
                printf("NO\n");
            }else{
                for(j=0;j<a;j++){
                    k=pow(2,j);
                    printf("%d\n",k);
                }
            }
        }
    }
	return 0;
}

I couldn’t get my mistake. I solved this problem but my code was always wrong. Anyone please help me

22

this is really helpful post for me thank you for sharing with us..