Hello coders, today we are going to solve Yet Another Flipping Problem Codechef Solution.
Problem
Chef has a binary string SS of length NN, where the first KK characters of SS are ’11’, while the rest are ’00’. He wants to make all the characters equal to ’00’. You are allowed to perform the following operation on the string SS as long as 2i−1≤N2i−1≤N:
- In the ithith operation, you can select any contiguous range of 2i−12i−1 indices of SS and flip their values.
He can use the above operation any number of times. If there is no sequence of operations that can convert the string to all ’00’s, print NONO.
Otherwise, print YESYES in the first line and then describe the operations. Print the starting indices of the contiguous range to be flipped in each operation. See Output Format for further details.
Input Format
- First line of the input will contain TT, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, two integers N,KN,K.
Output Format
For each test case, do the following:
- If there is no sequence of operations to convert each character of SS to ’00’, print NONO.
- Otherwise, print YESYES in the first line. (You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer)
- In the second line print MM, the number of operations you want to perform.
- Then print MM lines describing the operations. In the ithith line, print the starting index LL of the range [L,L+2i−1−1][L,L+2i−1−1] flipped in the ithith operation.
- The value of L+2i−1−1L+2i−1−1 should not exceed NN in any operation.
Constraints
- 1≤T≤50001≤T≤5000
- 1≤N≤1091≤N≤109
- 0≤K≤N0≤K≤N
Sample Input 1
3 5 0 3 3 2 2
Sample Output 1
YES YES 2 3 1 NO
Explanation
Test case 1: Since K=0K=0, all the characters of string SS are already ’00’. So, there is no need to perform any operation.
Test case 2: We have N=3N=3 and K=3K=3. So S=111S=111.
- In first operation, we can choose index 33 (21−1=121−1=1 indices) and flip it, giving S=110S=110.
- In the second operation, we can choose indices 1,21,2 (22−1=222−1=2 indices) and flip them, giving S=000S=000.
Therefore, we can make each character of SS to ’00’ by flipping index 33 in first operation and indices 11 and 22 in the second operation.
Yet Another Flipping Problem Codechef Solution in JAVA
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 0; tc < T; ++tc) {
int N = sc.nextInt();
int K = sc.nextInt();
System.out.println(solve(N, K));
}
sc.close();
}
static String solve(int N, int K) {
if (K == 0) {
return "YES\n0";
}
if (K % 2 == 0) {
return "NO";
}
List<Integer> startIndices = new ArrayList<>();
for (int i = 0; K != 0; ++i) {
int length = 1 << i;
if (K == length || (K & (1 << (i + 1))) != 0) {
startIndices.add(K + 1 - length);
} else {
int count = 0;
while ((K & (1 << (i + count + 1))) == 0) {
++count;
}
int pos = K + 1 - length;
for (int j = 0; j < count; ++j) {
pos -= 1 << (i + j);
startIndices.add(pos);
}
startIndices.add(pos);
i += count;
}
K -= length;
}
StringBuilder result = new StringBuilder("YES\n");
result.append(startIndices.size());
for (int startIndex : startIndices) {
result.append("\n").append(startIndex);
}
return result.toString();
}
}Yet Another Flipping Problem Codechef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef set<ll> si;
typedef map<ll,ll> mii;
typedef map<ii,ll> miii;
typedef map<char,int> mci;
typedef priority_queue <int> pq_g; //to store data in desecending order
typedef priority_queue <int, vector<int>, greater<int>> pq_s;
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define p(str) cout<<str;
#define pe(str) cout<<str<<"\n";
#define f(s,n,i) for(i=s;i<n;i++)
#define endl "\n"
#define vl(d) (ll)str[d]-48
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
int gcd(ll a,ll b){return (b==0?a:gcd(b,a%b)) ;}
int main()
{
fast;
ll T=1;
cin>>T;
while(T--)
{
ll N,M,Q,K,i,j,k=0,x,y,z,ind=0,sum=0,flag=0,count=0,mx=0,r=0,a,
b,c,mn=INT_MAX,sz=0,res=1;
cin>>N>>K;
if(!K){
YES cout<<0<<endl;
continue;
}
if(K%2==0){NO continue;}
for(i=31;i>=0;i--){
if(((1<<i)&K)!=0){
sz=i+1;
break;
}
}
K=(K+(1<<sz)-1)/2;
YES cout<<sz<<endl;
vi arr;
for(i=sz-2;i>=0;i--){
if(((1<<i)&K)!=0){
arr.pb(res);
res+=(1<<i);
}
else{
res-=(1<<i);
arr.pb(res);
}
}
for(i=sz-2;i>=0;i--)cout<<arr[i]<<endl;
cout<<res<<endl;
}
return 0;
}Yet Another Flipping Problem Codechef Solution in Python
import sys
import math
input = sys.stdin.readline
def solve():
n,k = map(int, input().split())
if k==0:
return "YES\n0"
elif k%2==0:
return "NO\n"
else:
for i in range(31,-1,-1):
if (1<<i)&k !=0:
x=i+1
break
k = (k+(1<<x)-1)//2
ans = "YES\n"
ans+=str(x)+"\n"
r = 1
arr = []
for i in range(x-2, -1,-1):
if (int(1<<i)&int(k))!=0:
arr.append(r)
r+=int(1<<i)
else:
r-=int(1<<i)
arr.append(r)
for i in range(x-2, -1,-1):
ans+=str(arr[i])+"\n"
ans+=str(r)
return ans
if __name__ == "__main__":
t = int(input())
# t=1
for _t in range(t):
k = solve()
print(k)Disclaimer: The above Problem (Yet Another Flipping) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
