Here is the link to the problem :
I wanted to discuss the final solution for 100bit strings. So basically what I tried to do was
that first of all get the first 10 bits as there cannot be any changes possible in it until the 11th query. Now, while doing this I stored the positions of 2 bits that are same as l_same and r_same and the position of 2 bits that are different as l_diff and r_diff. Note that I am extracting bits from the 2 ends of the string and not from the starting only or ending only. So if my any query extracts the ith bit then my next query extracts the (n-i+1th) bit. Now after the 10 queries, I do the following:
First, check if there were any same bits or not. If not then all the bits so far would be different from their counterpart from the other end of the string. So now I make 2 queries for that different positions of the string l_diff and r_diff. If they turn out to be the same as the previous ones then I don’t need to make any changes, if they are flipped then I don’t need to worry about complementation and reversal, I can do any one of them to account for it.
Now consider that there were some bits present which were same. In that case, first I make 2 queries for l_same and r_same, and check if the bits now received are the same as that stored in the positions l_same and r_same. If not then there definitely must be complementation. I do this then and there. Now to check if we also need to reverse the string, then we look for the different bits (l_diff and r_diff). I make 2 more queries for l_diff and r_diff. If they are same then nothing else needs to change, if they turn out to be opposite then just do a reversal also. Note that this reversal won’t affect the pair of bits that are same already.
After that, I just go on to make 6 or 8 more queries (according to the number of queries used in the above process). I would query 8 more times if above I used only 2 queries or 6 times if above I used 4 queries. I would continue to do this until I don’t reach the middle of the string. If I reach the middle of the string then my work is done.
Now I know this solution won’t work for the 100bit length string as the no. of queries would be slightly larger than 150 in some cases. But I can reduce that 4 queries for checking l_same, r_same and l_diff, r_diff to 2 only. This will work out in less than 150 queries.
However, when I tried to submit this it didn’t even work for the 20bits length string. I got the wrong answer to that. Can somebody discuss with me if my approach is correct or not, or if they have a better approach?
Here is my code for the same :
/*Priyansh Agarwal*/
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define nline "\n"
typedef long long ll;
typedef unsigned long long ull;
void flip(int *arr,int n)
{
for(int i=1;i<=(n+1)/2;i++)
{
int temp=arr[i];
arr[i]=arr[n-i+1];
arr[n-i+1]=temp;
}
}
void inversion(int *arr,int n)
{
for(int i=0;i<=n;i++)
arr[i]=arr[i]^1;
}
int helper(int l_same,int r_same,int l_diff,int r_diff,int* arr,int b)
{
if(l_same==-1)
{
//if received bits are different then clearly there is only reversal or inversion
//in this case both inversion or reversal will result in same answer so no need to worry
//if received bits are same then if it (complementation and reversal) or nothing we dont care
int l,r;
cout<<l_diff<<endl;
fflush(stdout);
char ch;
cin>>ch;
if(ch=='N')
return 0;
l=ch-48;
cout<<r_diff<<endl;
fflush(stdout);
cin>>ch;
if(ch=='N')
return 0;
r=ch-48;
if(!(arr[l_diff]==l && arr[r_diff]==r)) //checking for equality
flip(arr,b); //performing inversion as both comp and inv will result in same output
return 2;
}
else
{
//now clearly we will ask for the same bits
//if they are same then there can be no complementation
//if they are different then there must be atleast complementation
//we perform the complementation
//now we check the different bits, then now we need to do reversal also
//if they are same then no need to do anything else
int l,r;
cout<<l_same<<endl;
fflush(stdout);
char ch;
cin>>ch;
if(ch=='N')
return 0;
l=ch-48;
cout<<r_same<<endl;
fflush(stdout);
cin>>ch;
if(ch=='N')
return 0;
r=ch-48;
if(l==arr[l_same] && r==arr[r_same]) //no complementation
{
if(l_diff==-1)
return 2;
int l1,r1;
cout<<l_diff<<endl;
fflush(stdout);
char ch;
cin>>ch;
if(ch=='N')
return 0;
l1=ch-48;
cout<<r_diff<<endl;
fflush(stdout);
cin>>ch;
if(ch=='N')
return 0;
r1=ch-48;
if(!(arr[l_diff]==l1 && arr[r_diff]==r1))
flip(arr,b);
return 4;
}
else //complemenation necessary
{
if(l_diff==-1)
{
inversion(arr,b);
return 2;
}
int l1,r1;
cout<<l_diff<<endl;
fflush(stdout);
char ch;
cin>>ch;
if(ch=='N')
return 0;
l1=ch-48;
cout<<r_diff<<endl;
fflush(stdout);
cin>>ch;
if(ch=='N')
return 0;
r1=ch-48;
inversion(arr,b); //inversion means complementation here
if((arr[l_diff]==l1 && arr[r_diff]==r1))
flip(arr,b); //flip means reversal here
return 4;
}
return 4;
}
}
int main()
{
int t,b;
cin>>t>>b;
while(t--)
{
int *arr=new int[b+1];
for(int i=0;i<=b;i++)
arr[i]=1;
int l_diff=-1;
int r_diff=-1;
int l_same=-1;
int r_same=-1;
int n=b;
for(int i=1;i<=5;i++)
{
cout<<i<<endl;
fflush(stdout);
char ch;
cin>>ch;
if(ch=='N')
return 0;
arr[i]=ch-48;
cout<<n-i+1<<endl;
fflush(stdout);
cin>>ch;
if(ch=='N')
return 0;
arr[n-i+1]=ch-48;
if(arr[n-i+1]!=arr[i])
{
l_diff=i;
r_diff=n-i+1;
}
else
{
l_same=i;
r_same=n-i+1;
}
}
int queries=10;
int left=5;
while(left<b/2 && queries<150)
{
int m=helper(l_same,r_same,l_diff,r_diff,arr,b);
if(m==0)
return 0;
else
queries+=m;
while(queries%10!=0 && left<b/2)
{
left+=1;
cout<<left<<endl;
fflush(stdout);
char ch;
cin>>ch;
if(ch=='N')
return 0;
arr[left]=ch-48;
cout<<n-left+1<<endl;
fflush(stdout);
cin>>ch;
if(ch=='N')
return 0;
arr[n-left+1]=ch-48;
if(l_diff==-1 && arr[left]!=arr[n-left+1])
{
l_diff=arr[left];
r_diff=arr[n-left+1];
}
if(l_same==-1 && arr[left]==arr[n-left+1])
{
l_same=left;
r_same=n-left+1;
}
queries+=2;
}
}
string s="";
for(int i=1;i<=b;i++)
s+=char(arr[i]+48);
cout<<s<<endl;
fflush(stdout);
char ch;
cin>>ch;
if(ch=='N')
return 0;
}
return 0;
}