Nice Editorial
I think you are asking more than K queries that’s why it gives you a WA.
great editorial…wonderful way of explaining the solution!!!
2 Likes
If I remember correctly, this problem should stem from IMO2012. 
10 Likes
If we are removing the 2nd part we create a hole in the range. So we need to split the ranges and then query on both. That would not remove 1/4 part per 2 query?
I used the approach for 75 marks one but i could score only 45. please check my solution.
https://www.codechef.com/viewsolution/34157529
particularly this part
while(N>20)
{
p1=N/2;
printf(“%d\n”,v[p1]);
fflush(stdout);
scanf(" %c",&j);
if(j==‘E’)
return 0;
if(j==‘G’)
{
p2=N/4;
printf(“%d\n”,v[p2]);
fflush(stdout);
scanf(" %c",&k);
if(k==‘E’)
return 0;
if(k==‘G’)
{
v.erase(v.begin() + 1, v.begin() + p2+1);
N-=(p2);
continue;
}
else
{
v.erase(v.begin() + p2, v.begin() + p1+1);
N-=(p1+1-p2);
continue;
}
}
else
{
p2=3*N/4;
printf(“%d\n”,v[p2]);
fflush(stdout);
scanf(" %c",&k);
if(k==‘E’)
return 0;
if(k==‘L’)
{
v.erase(v.begin() + p2, v.end());
N=p2-1;
continue;
}
else
{
v.erase(v.begin() + p1, v.begin() + p2+1);
N-=(p2+1-p1);
continue;
}
}
}
for(i=1;i<=N;i++)
{
printf(“%d\n”,v[i]);
fflush(stdout);
scanf(" %c",&j);
if(j==‘E’)
return 0;
}
1 Like
How do you even remember that lol
1 Like
Maybe I did it in high school, then I found this problem very familiar. 
9 Likes
no…that would have given WA(-1.0000)
could you format “this part”?
“Since we are eliminating, all the plausible values are not in a contiguous range. We can maintain them as a list of valid ranges. Again, See setter’s code for more details.”
Quoting the editorial.
Can someone share a video explanation or explain the editorial’s gist in short
1 Like
It seems that the constraint K = 120 wasn’t tight. Because I remove 50% portion in 4 queries, but your method actually removes 55.55% in 4 queries.
Here is my solution to remove 50% in 4 queries :
1. Query N/2 : Let’s say we get G (If we get L,we can use similar strategy.)
2. Query N/3 :
If I get G, 33% is removed in 2 queries, so this case won’t appear.
If I get L, 16.66% is removed.
3. Query 2N/3 :
If I get L, 50% is removed in 3 queries, so this case won’t appear.
If I get G, more 16.66% is removed , so total 33.33% is removed.
4. Query N/6 : If get L or G, more 16.66% will be removed. So I get reduction of 50% in 4 queries.
4 Likes
Is this a right implementation ?
#include <iostream>
using namespace std;
#define ll long long int
ll ans;
#include<map>
map<ll,ll> m;
void bst(ll l,ll r)
{
ll mid = (l+r)/2;
ll mid1 = (l+r)/3;
char a1,a2;
cout<<mid<<endl;
cin>>a1;
if(a1=='E')
{
ans=1;
return;
}
cout<<mid1<<endl;
cin>>a2;
if(a2=='E')
return;
if(a1==a2 && a1=='L')
{
bst(l,mid);
}
if(a1==a2 && a1=='G')
{
bst(mid1,r);
}
if(a1=='G' && a2=='L')
{
bst(l,mid1);
bst(mid,r);
}
if(a1=='L' && a2=='G')
{
bst(l,r);
}
}
int main() {
ll n;
cin>>n;
bst(1,n);
return 0;
}
I’m getting WA. Please help me
I agree I recall too!
1 Like
It’s somewhat relieving to know that I was close, got the same idea with cutting in half, then quarters: CodeChef: Practical coding for everyone however it didn’t work as expected, as I was confused to take all possibilities into account: true or false answers + maybe a change of the number in between the queries. The fact that the hidden number can change at any time (under the condition to preserve the validity of all answers already given, as per the rules) really confused me.
Also, for case 1 I think that the following solution has a good educational value, and is pretty obvious: just run in an alternating manner two binary searches, one asking only odd-numbered questions, and the other asking only even-numbered questions: CodeChef: Practical coding for everyone
One of them is doomed to always receive truthful answers. Care must be taken for both searches to always consume one question to preserve the condition above: this means that if the main loop has exited (likely due to receiving some lies in the questions asked), a dummy question needs to be asked.
Finally, I got solutions for both case1 and case2, but failed to combine them into one that solves both cases. It is a bit disappointing that randomisation is capable of solving them both.
1 Like
Partial Solution (15 pts)
Just in case someone wants help on how to use the odd-even information to get started.
The trick lies in first querying 1 to check whether evenLie or oddLie pattern is being followed.
Can anyone please tell me why did i get 15 points only as some of the tasks of subtasks 2 and 3 have an AC.
#include<bits/stdc++.h>
using namespace std;
char getResponse(int display){
cout << display << '\n';
string response;
cin >> response;
if(response[0]=='E')exit(0);
return response[0];
}
struct interval{
int s,e,l;
};
struct interval_storer{
vector<interval> v;
int len_v;
int gap(){
len_v = v.size();
int g = 0;
for(int i=0;i<len_v;i++) g+=v[i].l;
return g-1;
}
int findith(int n){
int i=0;
while(i<len_v){
if(n-v[i].l<0)return v[i].s+n;
n-=v[i].l;
i++;
}
}
vector<interval> getFromLeftTill(int n){
int i=0;
vector<interval> temp;
while(i<len_v){
if(v[i].e>n){
if(v[i].s<=n)temp.push_back({v[i].s,n,n-v[i].s+1});
return temp;
}
temp.push_back(v[i]);
i++;
}
}
vector<interval> getFromRightTill(int n){
int i=len_v-1;
vector<interval> temp;
while(i>=0){
if(v[i].s<n){
if(v[i].e>=n)temp.push_back({n,v[i].e,v[i].e-n+1});
reverse(temp.begin(),temp.end());
return temp;
}
temp.push_back(v[i]);
i--;
}
}
};
interval_storer A;
void bs(){
int g = A.gap();
if(g<=8){
for(auto i : A.v){
for(int j=i.s;j<=i.e;j++)char resp = getResponse(j);
}
}
int mid1 = A.findith(g/3);
int mid2 = A.findith(g-g/3);
char resp1 = getResponse(mid1);
if(resp1=='G'){
resp1 = getResponse(mid1);
if(resp1=='G'){
vector<interval> rrr = A.getFromRightTill(mid1);
A.v.clear();
for(auto i : rrr)A.v.push_back(i);
bs();
return;
}
}
char resp2 = getResponse(mid2);
if(resp2=='L'){
vector<interval> lll = A.getFromLeftTill(mid2);
A.v.clear();
for(auto i : lll)A.v.push_back(i);
bs();
}
else{
vector<interval> lll = A.getFromLeftTill(mid1);
vector<interval> rrr = A.getFromRightTill(mid2);
A.v.clear();
for(auto i : lll)A.v.push_back(i);
for(auto i : rrr)A.v.push_back(i);
bs();
}
}
int main() {
int n;
cin >> n;
A.v.push_back({1,n,n});
bs();
}
2 Likes