GUESSG - Editorial

[nishant403]

@carre Can you help me in this ?

[manvir1350]

best editorial i had ever read on code chef till date.

[carre]

I think you just said it. I wouldn’t know how to prepare a checker to simultaneously block many different strategies. The alternative is not to simultaneously block many strategies, but to “learn” which one is used and block it, but that could be a great effort. Probably, if I were the setter, I wouldn’t do it even if I knew how.

[beyond_edit]

Hey,

Thanks. I get it. It was due to TLE. erasing and copying in vector caused O(n) for each query. Thanks

[nishant403]

Basic assumptions about checker :

1. If you have detetmined that X must be greater or less than some value, checker will always tell truth there.

2. Repeatedly asking for single number will always give alternate answers.

3. Choose the ‘G’ or ‘L’ such that least segment size gets “determined”. In case of equality, choose ‘G’ if integer asked is in left to middle and ‘L’ if it is in right to middle.

4. Answer will become ‘E’ only when the last remaining integer is asked.

I think these are enough to get the worst case of most strategies.

[sachinssn]

this is a really beautiful way of writing an editorial, great work

[codificador]

I envy you for those 45 points. LOL!

[wickedknight]

uff

[krn05]

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++;
}
}

[diegohdmgz]

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

1. 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)

2. 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.

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

[auto_genos]

The explanation is really good.

[sidhant_jain]

Can anyone please tell why my code is not working for 75 points?
https://www.codechef.com/viewsolution/34405931

[marro_mujhe]

This solution to GUESSG in JUN20B long challenge should not pass

See the solution given below : THE SOLUTION He just asked queries at left boundary and as a LIE i.e ‘L’ was returned then he queried the mid and erased the half of the search space . If this type of solution gets accepted then it is clearly a glitch in judging. P.S. This solution got AC for 75 Points!!! P.S. Writter did not even flush the output stream!!!

Please see the post. It contains a naive solution to GUESSGwhich got accepted for 75 points and does not deserve to be.

[ayush_jha9669]

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

[navpahul551]

I was also surprised when i got those.

[chetas411]

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!!

[h_sh]

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;
}

[techfreak_19]

It’s the same. Solution without lambda expression using standard functions - CodeChef: Practical coding for everyone

[reena_code_123]

Maybe the judge followed simple strategy and lied odd results!
…

[ben_956_78]

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

solution but Disabled

`