uff
I am not able to identify why this code is failing for subtask 1. A small help will be much appreciated. Thank you
#include <bits/stdc++.h>
#define ll long long int
#define foro(i,n) for(ll i=0;i<n;i++)
#define forv(i,n) for(ll i=1;i<=n;i++)
using namespace std;
int main(){
ll n;
cin>>n;
ll k=1;
ll low1=1, high1=n, low2=1, high2=n;
while(k<=300){
if(k%2==0){
ll mid=(low1+high1)/2;
char st;
cout<<mid<<endl;
cin>>st;
if(st=='E'){
break;
}
else if(st=='L'){
low1=mid+1;
}
else if(st=='G'){
high1=mid-1;
}
}
else if(k%2!=0){
ll mid=(low2+high2)/2;
char st;
cout<<mid<<endl;
cin>>st;
if(st=='E'){
break;
}
else if(st=='L'){
low2=mid+1;
}
else if(st=='G'){
high2=mid-1;
}
}
k++;
}
}I will share my approach, maybe someone find it useful. I’ll show how to reduce an interval of length N to an interval of length at most 5N / 8 with at most 3 queries
-
First, query at N/2. WLOG assume that the answer to the query is G (if it’s not , do the next steps but in opposite direction)
-
Query at 3N / 8
- If the answer to the query is G you can eliminate the left part (because both query point to the same direction so the second query has to be true) and keep just 5N/8 of the interval. So you’re done with 2 queries
- If the answer to the query is L , you can eliminate the middle part because both of the queries can’t be true at the same time so one of these queries is a lie .But is not enough, so go to Step 3.
- Query at 3N / 4
- If the answer to the query is L you can eliminate the right part. Because query 2 and query 3 point to the same direction so query 3 has to be true. So you just keep 3N/8 + N/4 = 5N/8 and you’re done
- If the answer to the query is G you can eliminate the middle part of query 2 and 3 because just one of them can be true. So again you just keep 3N/8 + N/4 = 5N/8 and you’re done.
So in the worst case the number of queries you need is roughly 3log_{\space 8/5}{\space n}. For 10^9 it’s roughly 133 with that formula, but it is a little bit less. I used dp to calculate the number of queries in the worst case with my strategy and it gave me 124 or 125 queries (I don’t remember). I was just 5 queries away from target , so I decided that in each query (for example when we query N / 2 , 3N/8 , 3N/4) maybe I can try querying a little bit more or less than the value I was asking in my strategy, for example trying N/2 + 1 or even N/2 + 7 . So I simulate this process in my dp and I stored the best choice.
Surprisingly, my dp showed that in worst case the minimum number of queries with this strategy was 120. So each time I ask a query, I used the best choice that my dp suggests and I got AC.
Last but not least, to handle the part of erasing some ranges, we can maintain a list of valid ranges as the editorial says but I thought this approach could be error-prone so I decided to code an Implicit Segment Tree doing assignment on range (overkill).
Link to my solution : CodeChef: Practical coding for everyone
3 Likes
The explanation is really good.
Can anyone please tell why my code is not working for 75 points?
https://www.codechef.com/viewsolution/34405931
Please see the post. It contains a naive solution to GUESSGwhich got accepted for 75 points and does not deserve to be.
Not Exactly, that was regarding finding ranges and also it required to prove the number of operations required to get the correct range instead of guessing the number
1 Like
I was also surprised when i got those.
Is it difficult to solve this problem without using lambda expressions as incorporated in the tester’s code? Where to learn lambda expressions in c++ from ? please suggest!!
Can you help me figuring out error ?
#include <iostream>
using namespace std;
#define ll long long int
ll ans;
#include<map>
map<ll,ll> m;
void bst(ll l,ll r)
{
if(l>=1 && r>=1)
{
}
else
return;
ll mid = (l+r)/2;
ll mid1 = (l+r)/3;
ll mid2 =(mid+r)/2;
char a1,a2,a3;
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);
}
cout<<mid2<<endl;
cin>>a3;
if(a3=='E')
return;
if(a1=='G' && a2=='L' && a3=='L')
{
bst(mid,mid2);
bst(l,mid1);
// bst(mid,mid2);
}
if(a1=='G' && a2=='L'&& a2=='G')
{
bst(l,mid1);
bst(mid2,r);
}
if(a2=='G' && a1=='L' && a3=='L')
{
bst(mid1,mid2);
// bst(l,mid1);
// bst(mid,mid2);
}
if(a2=='G' && a1=='L'&& a2=='G')
{
// bst(l,mid1);
bst(mid1,r);
}
}
int main() {
ll n;
cin>>n;
bst(1,n);
return 0;
}
It’s the same. Solution without lambda expression using standard functions - CodeChef: Practical coding for everyone
Maybe the judge followed simple strategy and lied odd results!
…
Earlier logic 
:
Let N=100
query N/2 i.e., 50 repeatedly, till I got same answer (two times ‘L’ or ‘G’)
example : I got “L G L G L G L L” finally I got two L L continuously since they can’t lie two times
in a row. So number will be less than 50
If I got ‘L’ then my new range will be 1 to N/2-1
if I got ‘G’ then I will select N/2+1 to N
This process repeat continuously , however I got only 15% don’t know the reason
`
@ben_956_78 What if two consecutive answers never repeat, for eg. grader tells truth and lie alternatively
https://dl.acm.org/doi/pdf/10.1145/167088.167129
This almost gave the answer… but not really! xD
1 Like
Yes, I did notice that(For nearly a week). Thanks for pointing it out. 
Hey can you give the links of questions of similar ideology for practice
1993，so old 
Can the grader lie if i ask him the same query?