PROBLEM LINK:
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