GTN - Editorial

PROBLEM LINK:

Contest
Practice

Setter- Raushan Kumar
Tester- Jatin Nagpal
Editorialist- Raushan Kumar

DIFFICULTY:

Easy-Medium

PRE-REQUISITES:

Binary Search and Observation

PROBLEM:

Chef has an array whose elements are unknown to you, you need to figure out whether an element X exists in it or not, if Yes find out its location. You can ask at-most q queries.

Imp:- m is an index for which you are asking a query, and for this query Chef will return sum of K elements starting from m to m + K – 1, where K = 2^{i} , i is the maximum value of integer

EXPLANATION:

There are three conditions possible- X is present at odd position or X is present at even position or X is not present in the array

Case 1 : ‘X’ is at odd position

Since array is sorted, if you ask for an odd ‘m’ then K will always be 1, so now you can perform binary search, but a thing is that you must perform binary search on Chef’s array by asking for an odd m.

For subtask 3, N is unknown

So, consider N=1000000 (as per maximum value of N in constraints)

Now you can perform a binary search

If m turns out even, then just decrease m by 1 or increase m by 1

Now compare the value of X to the value which has been returned by Chef

Then we can decide in which half should we go, as we do in binary search

And doing so you can find out the element present at any odd index and you can easily find out at which index X is present

Case 2 : when X is present at even index or not present in the array

NOTE: X may be not present in the array but we only come to know this when we figure out the value present at this index

So now here is the game, X is present at even index say I

So again, a thing is here that you can reach at both side odd indices of that even index I by performing binary search at odd index as we have done in case 1

Now all we have to do is to find out whether X is present at index I in array or not

Now if we will ask for m = I then we will have sum of K elements from I to I+K-1, we can discard sum of last (K/2) element by asking for m = I +(K/2) now we have sum of K/2 element and again we can discard sum of last (K/4) element by asking m = I+(K/4)

so here is the generalized form of index for which we must ask query

m = I+(K/b)

where b = 2,4,8……….K. (as we know K is an integer power of 2 so it will come in this sequence)

let’s see an example

chef has given X which is present at index 24 or not present in an array

By performing binary search, we can come at index at 23 and 25 now we know either X will be at this index 24 or not present in the array, so we must find out the number which is present at index 24

If we will ask for m = 24 (here K is 8)

Chef will return sum of A[24:31]

Now m = 24+(8/2)

Chef will return sum of A[28:31]

Now we are left with the sum of A[24:31]-A[28:31] = A[24:27]

Now m = 24+(8/4)

Chef will return sum of A[26:27]

Now we are left with the sum of A[24:27]-A[26:27] = A[24:25]

Now m = 24+(8/8)

Now we are left with the sum of A[24:25]-A[25:25] = A[24:24]

Now we know the element which is present at index 24

SOLUTION

Setter
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll even(ll q)
{
   int degree;
   ll start=q,end,s,fs;
   for(int i=0;i<18;i++)
   {
        if(q>>i&1)
        {
            degree=i;
            break;
        }
    }
    degree=pow(2,degree);
    cout<<"1"<<" "<<q<<endl;
    cin>>fs;
    end=q+degree;
    while(q%2==0)
    {
        q=(start+end)/2;
        cout<<"1"<<" "<<q<<endl;
        cin>>s;
        fs-=s;
        end=q;
    }
    return fs;   
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,x,start,end,mid,s;
        string res;
        cin>>n;
        cin>>x;
        start=1;
        end=n;
        if(n==-1)
            end=1000000;
  
        while(start<=mid)
        {
            mid=(start+end)/2;
            if(mid%2==0)
               mid+=1;
            if(end-start==2)
            {
                 mid-=1;
                 s=even(mid);
                 break;
            }
            cout<<"1"<<" "<<mid<<endl;
            cin>>s;
            if(s==0)
            {
               end=mid;   
            }
            else
            {
                if(x>s)
                    start=mid;
                else if(x<s)
                    end=mid;
                if(x==s)
                {
                    break;
                }
            }
        }
        if(x==s)
        {
            cout<<"2"<<" "<<mid<<endl;
            cin>>res;
            if(res=="YES")
                continue;
            else
                break;    
        }
        else
        {  
            cout<<"2"<<" "<<"-1"<<endl;
            cin>>res;
            if(res=="YES")
                continue;
            else
                break;        
        }   
    }
    return 0;
}
Tester
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
#define mod 1000000007
int dp[1000005];
int in(int j)
{
	if(dp[j]!=-1)
		return dp[j];
	int ret;
	cout<<"1 "<<j<<endl;
	cin>>ret;
	return dp[j]=ret;
}
int query(int mid)
{
	int j=mid;
	int k=1;
	int ret=0;
	while(j%2==0)
	{
		j/=2;
		ret-=in(mid+k);
		k*=2;
	}
	return ret+in(mid);
}
int32_t main()
{
	int t;
	cin>>t;
	while(t--)
	{
		f(i,0,1000005)
			dp[i]=-1;
		int n,x;
		cin>>n>>x;
		int st=1,en=(1<<20)+1;
		int ans=-1;
		while(st<=en)
		{
			int mid=(st+en)/2;
			if(mid%2==0)
			{
				mid++;
				if(en<mid)
					mid--;
			}
			int val=query(mid);
			if(val==0)
				val=mod;
			if(val>x)
			{
				en=mid-1;
			}
			else if(val<x)
			{
				st=mid+1;
			}
			else
			{
				ans=mid;
				break;
			}
		}
		cout<<"2 "<<ans<<endl;
		string in;
		cin>>in;
	}
	
	return 0;
}

TIME COMPLEXITY

q<=log2(N)+(some more query)

if X is present at an even index or not present in array then we have to ask log2(K) more query (K is for that even index on which X is present or may be not)

Feel free to share your approach :slightly_smiling_face:

3 Likes

Thanks for the problem! During the contest, I, however, was unable to get an AC in spite of having a correct solution simply because the string I was checking for was “Yes” (and as I see in the setter’s code it should have been “YES”). Later, when I removed that check I got an AC after the contest.

during contest
after contest

Setter code is also giving wrong answer.i think his code is failing when number is at index 1