PROBLEM LINK:
Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest
Author and Editorialist: Jay Sharma
Testers: Shubham Anand Jain, Aryan Choudhary
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary Search, Observations, Geometry
PROBLEM:
You need to guess the coordinates of a hidden integer point lying in the XY plane. You can make two types of queries -
- Query a single point. In this case, the grader tells you which quadrant or axis the queried point lies in with respect to the hidden point. If both the points are same, the task is solved.
- Query a rectangle with sides parallel to the axes. In this case, the grader tells you whether the hidden point lies strictly inside, strictly outside or on the perimeter of the queried rectangle. If the hidden point lies on the perimeter, the task is solved.
If your guess was incorrect, the hidden point moves exactly D units in any of the four axis-parallel directions. D is fixed and is known to be either 0 or 1 but the direction is unknown and may vary for different queries.
You can ask upto Q queries to solve the task.
SOME HINTS:
Hint 1
Any randomised solution will not work as the grader is adaptive.
Hint 2
Did you get an intuition for Binary Search?
Hint 3
How to handle the shifting of the point in an easy way?
Solution
Decrease the lower bound of the search space and increase the upper bound of the search space by D for both the dimensions.
Hint 4
Can the point be completely guessed using binary search only?
Answer
No, the search space can only be reduced upto 4\times 4 using binary search.
Hint 5
Use Type 2 queries to reduce the search space further.
Hint 6
Aren’t some points being over-included in the search space?
Answer
Yes, the four corner points cannot be in the search space since the movement of the point is along one direction only and these corner points are unreachable from any of the points in the previous search space.
QUICK EXPLANATION:
Do a parallel binary search for the point over both the dimensions using the first type of query. To account for the shift in the position, decrease the lower bound and increase the upper bound of the search space for both the dimensions by D. This way, the search space can be reduced to a 4\times 4 grid. Then use a hard-coded sequence of queries (see explanation for details) to get the exact location of the point.
EXPLANATION:
Let’s start with the first subtask where the truck doesn’t move. This problem can be solved by applying a parallel binary search for the point over both the dimensions simultaneously. A pseudocode for the same is given below -
Parallel Binary Search Implementation
long long INF = 1e+18;
long long lx=-INF,rx=INF;
long long ly=-INF,ry=INF;
while(true)
{
long long mx=(lx+rx)/2;
long long my=(ly+ry)/2;
cout << "1 " << mx << " " << my << endl;
string s;
cin >> s;
if(s=="O")
break;
else if(s=="XP")
{
lx=rx=mx;
ry=my-1;
}
else if(s=="XN")
{
lx=rx=mx;
ly=my+1;
}
else if(s=="PY")
{
ly=ry=my;
rx=mx-1;
}
else if(s=="NY")
{
ly=ry=my;
lx=mx+1;
}
else if(s=="PP")
{
rx=mx-1;
ry=my-1;
}
else if(s=="PN")
{
rx=mx-1;
ly=my+1;
}
else if(s=="NP")
{
lx=mx+1;
ry=my-1;
}
else if(s=="NN")
{
lx=mx+1;
ly=my+1;
}
}
Query Analysis
Let us analyse for X coordinate. Y coordinate can be analysed similarly. Let S_x(i) denote rx-lx+1 after the i-th query. Lets us call this as the search space the for X coordinate. Then the function S_x follows the following recurrence -
S_x(0)=2\times10^{18}+1,
S_x(i+1)=\frac{S_x(i)-1}{2} if S_x(i) is odd and
S_x(i+1)=\frac{S_x(i)}{2} if S_x(i) is even.
It is not hard to see that S_x(i)=0 for i\geq 61. Thus, we require 61 queries in the worst case to guess the point. This is well within the limit of 72 queries.
Now let’s extend this idea of parallel binary search for D=1. Since, we don’t know which direction the truck will go, we need to consider all the 4 cases. This can be done by decreasing both lx and ly by 1 and increasing both rx and ry by 1.
Now, the search space follows the recurrence -
S_x(0)=2\times10^{18}+1,
S_x(i+1)=\frac{S_x(i)+3}{2} if S_x(i) is odd and
S_x(i+1)=\frac{S_x(i)+4}{2} if S_x(i) is even.
The problem here is that if S_x(i)=4 then S_x(i+1)=4 and if S_x(i)=3 then S_x(i+1)=3. So, the search space cannot be reduced beyond 4 or 3 and here comes the role of Type 2 attacks.
I will be describing the optimal solution here which uses 64 queries. For the sub-optimal solutions for Subtasks 2 and 3, refer to the Subtasks section.
First, we will reduce the search space to 5\times 5. Exactly 60 Type 1 queries will be used in the worst case.
Proof
Lemma 1: Any search space of the form 2^k+4 can be reduced to a search space of 5 using exactly k queries.
Proof by induction
Base Case - A search space of 6 (=2^1+4) is reduced to a search space of \frac{6+4}{2}=5 using 1 query.
Induction hypothesis - Let a search space of 2^k+4 be reduced to a search space of 5 using exactly k queries.
Inductive Step - A search space of 2^{k+1}+4 can be reduced to a search space of \frac{2^{k+1}+4+4}{2} = 2^k+4 using 1 query which can be reduced to a search space of 5 using k queries. So, a search space of 2^{k+1}+4 can be reduced to a search space of 5 using exactly k+1 queries.
Lemma 2: Any search space of the form 2^k+3 can be reduced to a search space of 5 using exactly k-1 queries.
Proof by induction
Base Case - A search space of 7 (=2^2+3) is reduced to a search space of \frac{7+3}{2}=5 using 1 query.
Induction hypothesis - Let a search space of 2^k+3 be reduced to a search space of 5 using exactly k-1 queries.
Inductive Step - A search space of 2^{k+1}+3 can be reduced to a search space of \frac{2^{k+1}+3+3}{2} = 2^k+3 using 1 query which can be reduced to a search space of 5 using k-1 queries. So, a search space of 2^{k+1}+3 can be reduced to a search space of 5 using exactly k queries.
Since 2^{60}+4\leq 2\times 10^{18}+1\leq 2^{61}+3, a search space of 2\times 10^{18}+1 can be reduced to a search space of 5 using exactly 60 queries.
After this, the search space will be as follows -
Use a Type 1 attack at the center point as follows -
The worst case is when the truck was at one of the quadrant points. In each case, the new search space will be (Black points are in the search space and Red ones are not) -
Now, use a Type 2 attack as follows -
The worst case is when the truck was either inside or outside the rectangle. In each of these cases, the new search space will be -
Now, use a Type 2 attack as follows -
Once again, the worst case is when the truck was either inside or outside the rectangle. In each of these cases, the new search space will be -
All the points in this search space lie on the perimeter of the rectangle. So, we can finish the task by making a Type 2 attack as follows -
Total number of queries used =60+4=64
ALTERNATIVE SOLUTIONS (SUBTASKS):
Subtask 3
First, reduce the search space to 5\times 5 using parallel binary search. As mentioned above, this requires 60 queries.
Then make a Type 2 attack as below -
There are two cases to consider -
Case 1 - IN
The new search space will be -
Make a Type 2 attack as below -
Case 2 - OUT
The new search space will be -
Make a Type 1 attack as below -
In each of these cases, the worst case occurs when the point lies on a 3\times 1 region and the new search space will be -
Now, make a Type 1 attack as below -
In the worst case, the new search space will be -
This can be solved using 2 more queries as shown for the original constraints.
Total number of queries used = 60+3+2=65.
Subtask 2
First reduce the search space to 4\times 4 using Parallel Binary Search. This will require 61 queries. The search space will be -
Now, make a Type 2 attack as below -
The case for IN is easy to handle. Let’s see the case for OUT.
The new search space will be -
Now, use a Type 1 attack as follows -
The worst case is when we get XN. In this case, the new search space will be -
This can be solved using 3 queries as shown in the solution for Subtask 3.
Total queries required = 61+2+3=66.
SOLUTIONS:
Setter's Solution (in C++)
//Problem - Destroy The EMP Chip
//Author - Jay Sharma (jay_1048576)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
bool binarysearch(long long &lx,long long &rx,long long &ly,long long &ry)
{
long long mx=(lx+rx)/2;
long long my=(ly+ry)/2;
cout << "1 " << mx << " " << my << endl;
string s;
cin >> s;
if(s=="O")
return true;
else if(s=="XP")
{
lx=rx=mx;
ry=my-1;
}
else if(s=="XN")
{
lx=rx=mx;
ly=my+1;
}
else if(s=="PY")
{
ly=ry=my;
rx=mx-1;
}
else if(s=="NY")
{
ly=ry=my;
lx=mx+1;
}
else if(s=="PP")
{
rx=mx-1;
ry=my-1;
}
else if(s=="PN")
{
rx=mx-1;
ly=my+1;
}
else if(s=="NP")
{
lx=mx+1;
ry=my-1;
}
else if(s=="NN")
{
lx=mx+1;
ly=my+1;
}
return false;
}
void solve3x3(long long x,long long y)
{
cout << "2 " << x-1 << " " << y-1 << " " << x+1 << " " << y+1 << endl;
string s;
cin >> s;
if(s=="O")
return;
}
void solve3x4(long long lx,long long rx,long long ly,long long ry)
{
cout << "2 " << lx << " " << ly << " " << rx << " " << ry-1 << endl;
string s;
cin >> s;
if(s=="O")
return;
else if(s=="IN")
solve3x3(lx+1,ly+1);
else if(s=="OUT")
solve3x3(lx+1,ry);
}
void solve4x3(long long lx,long long rx,long long ly,long long ry)
{
cout << "2 " << lx << " " << ly << " " << rx-1 << " " << ry << endl;
string s;
cin >> s;
if(s=="O")
return;
else if(s=="IN")
solve3x3(lx+1,ly+1);
else if(s=="OUT")
solve3x3(rx,ly+1);
}
void solve4x4(long long lx,long long rx,long long ly,long long ry)
{
cout << "2 " << lx << " " << ly << " " << rx << " " << ry-1 << endl;
string s;
cin >> s;
if(s=="O")
return;
else if(s=="IN")
solve4x3(lx,rx,ly,ly+2);
else if(s=="OUT")
solve4x3(lx,rx,ly+2,ry+1);
}
void solve5x5(long long lx,long long rx,long long ly,long long ry)
{
rx=lx+4;
ry=ly+4;
long long mx = (lx+rx)/2;
long long my = (ly+ry)/2;
cout << "1 " << mx << " " << my << endl;
string s;
cin >> s;
if(s=="O")
return;
else if(s=="XP")
solve3x4(mx-1,mx+1,ly-1,my);
else if(s=="XN")
solve3x4(mx-1,mx+1,my,ry+1);
else if(s=="PY")
solve4x3(lx-1,mx,my-1,my+1);
else if(s=="NY")
solve4x3(mx,rx+1,my-1,my+1);
else if(s=="PP")
solve4x4(lx-1,mx,ly-1,my);
else if(s=="PN")
solve4x4(lx-1,mx,my,ry+1);
else if(s=="NP")
solve4x4(mx,rx+1,ly-1,my);
else if(s=="NN")
solve4x4(mx,rx+1,my,ry+1);
}
int main()
{
int tt,qu,d;
cin >> tt >> qu >> d;
while(tt--)
{
if(d==0)
{
long long lx=-INF,rx=INF;
long long ly=-INF,ry=INF;
while(true)
{
if(binarysearch(lx,rx,ly,ry))
break;
}
}
else
{
long long lx=-INF,rx=INF;
long long ly=-INF,ry=INF;
bool done=false;
while(rx-lx+1>5||ry-ly+1>5)
{
if(binarysearch(lx,rx,ly,ry))
{
done=true;
break;
}
else
{
lx--;
rx++;
ly--;
ry++;
}
}
if(!done)
{
solve5x5(lx,rx,ly,ry);
}
}
}
return 0;
}
Setter's Solution (in Java)
//Problem - Destroy The EMP Chip
//Author - Jay Sharma (jay_1048576)
import java.util.Scanner;
class CHAOSEMP
{
static Scanner sc = new Scanner(System.in);
static long INF = 1000000000000000000l;
static long lx,rx,ly,ry;
static boolean binarysearch()
{
long mx=(lx+rx)/2;
long my=(ly+ry)/2;
System.out.println("1 "+mx+" "+my);
System.out.flush();
String s = sc.next();
if(s.equals("O"))
return true;
else if(s.equals("XP"))
{
lx=rx=mx;
ry=my-1;
}
else if(s.equals("XN"))
{
lx=rx=mx;
ly=my+1;
}
else if(s.equals("PY"))
{
ly=ry=my;
rx=mx-1;
}
else if(s.equals("NY"))
{
ly=ry=my;
lx=mx+1;
}
else if(s.equals("PP"))
{
rx=mx-1;
ry=my-1;
}
else if(s.equals("PN"))
{
rx=mx-1;
ly=my+1;
}
else if(s.equals("NP"))
{
lx=mx+1;
ry=my-1;
}
else if(s.equals("NN"))
{
lx=mx+1;
ly=my+1;
}
return false;
}
static void solve3x3(long x,long y)
{
System.out.println("2 "+(x-1)+" "+(y-1)+" "+(x+1)+" "+(y+1));
System.out.flush();
String s = sc.next();
if(s.equals("O"))
return;
}
static void solve3x4(long x1,long x2,long y1,long y2)
{
System.out.println("2 "+x1+" "+y1+" "+x2+" "+(y2-1));
System.out.flush();
String s = sc.next();
if(s.equals("O"))
return;
else if(s.equals("IN"))
solve3x3(x1+1,y1+1);
else if(s.equals("OUT"))
solve3x3(x1+1,y2);
}
static void solve4x3(long x1,long x2,long y1,long y2)
{
System.out.println("2 "+x1+" "+y1+" "+(x2-1)+" "+y2);
System.out.flush();
String s = sc.next();
if(s.equals("O"))
return;
else if(s.equals("IN"))
solve3x3(x1+1,y1+1);
else if(s.equals("OUT"))
solve3x3(x2,y1+1);
}
static void solve4x4(long x1,long x2,long y1,long y2)
{
System.out.println("2 "+x1+" "+y1+" "+x2+" "+(y2-1));
System.out.flush();
String s = sc.next();
if(s.equals("O"))
return;
else if(s.equals("IN"))
solve4x3(x1,x2,y1,y1+2);
else if(s.equals("OUT"))
solve4x3(x1,x2,y1+2,y2+1);
}
static void solve5x5(long x1,long x2,long y1,long y2)
{
x2=x1+4;
y2=y1+4;
long mx = (x1+x2)/2;
long my = (y1+y2)/2;
System.out.println("1 "+mx+" "+my);
System.out.flush();
String s = sc.next();
if(s.equals("O"))
return;
else if(s.equals("XP"))
solve3x4(mx-1,mx+1,y1-1,my);
else if(s.equals("XN"))
solve3x4(mx-1,mx+1,my,y2+1);
else if(s.equals("PY"))
solve4x3(x1-1,mx,my-1,my+1);
else if(s.equals("NY"))
solve4x3(mx,x2+1,my-1,my+1);
else if(s.equals("PP"))
solve4x4(x1-1,mx,y1-1,my);
else if(s.equals("PN"))
solve4x4(x1-1,mx,my,y2+1);
else if(s.equals("NP"))
solve4x4(mx,x2+1,y1-1,my);
else if(s.equals("NN"))
solve4x4(mx,x2+1,my,y2+1);
}
public static void main(String[] args)
{
int tt = sc.nextInt();
int qu = sc.nextInt();
int d = sc.nextInt();
while(tt--!=0)
{
if(d==0)
{
lx=-INF;
rx=INF;
ly=-INF;
ry=INF;
while(true)
{
if(binarysearch())
break;
}
}
else
{
lx=-INF;
rx=INF;
ly=-INF;
ry=INF;
boolean done=false;
while(rx-lx+1>5||ry-ly+1>5)
{
if(binarysearch())
{
done=true;
break;
}
else
{
lx--;
rx++;
ly--;
ry++;
}
}
if(!done)
{
solve5x5(lx,rx,ly,ry);
}
}
}
}
}
Tester's Solution
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define rforn(i,s) for(int i=s;i>=0;--i)
#define rforsn(i,s,e) for(int i=s;i>=e;--i)
#define bitcount(a) __builtin_popcount(a) // set bits (add ll)
#define ln endl
#define getcurrtime() cerr<<"Time = "<<((double)clock()/CLOCKS_PER_SEC)<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
out<<"{ ";
forstl(x,c) out<<x<<" ";
out<<"}"; return out;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM=2e5+5,MOD=1e9+7;
const ld EPS = 1e-9;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void query1(ll x, ll y){
cout<<1<<" "<<x<<" "<<y<<ln;
}
void query2(ll xl, ll xr, ll yl, ll yr){
cout<<2<<" "<<xl<<" "<<yl<<" "<<xr<<" "<<yr<<ln;
}
void solve2x(ll xl, ll xr, ll yl, ll yr){
query2(xl, xr, yl, yr);
string ans;
cin>>ans;
assert(ans == "O");
return;
}
void solve33(ll xl, ll xr, ll yl, ll yr){
while(true){
query2(xl, xr, yl, yr);
string ans;
cin>>ans;
if(ans == "O") return;
}
}
void solve34(ll xl, ll xr, ll yl, ll yr){
if(yr-yl > xr-xl){
query2(xl, xr, yl, yr-1);
}
else{
query2(xl, xr-1, yl, yr);
}
string ans;
cin>>ans;
if(ans == "O") return;
if(ans == "IN"){
if(yr-yl > xr-xl){
return solve33(xl, xr, yl, yr-1);
}
else{
return solve33(xl, xr-1, yl, yr);
}
}
if(yr-yl > xr-xl){
return solve33(xl, xr, yr-1, yr+1);
}
else{
return solve33(xr-1, xr+1, yl, yr);
}
}
void solve44(ll xl, ll xr, ll yl, ll yr){
query2(xl, xr, yl, yr-1);
string ans;
cin>>ans;
if(ans == "O") return;
if(ans == "IN"){
return solve34(xl, xr, yl, yr-1);
}
return solve34(xl, xr, yr-1, yr+1);
}
int main(){
// fastio;
int tests, q, d;
cin>>tests>>q>>d;
// assert(q == 72);
// assert(d == 0);
// tests = readIntSp(2048, 2048);
// q = readIntSp(64, 72);
// d = readIntLn(0, 1);
while(tests--){
ll xl = -1e18;
ll xr = 1e18;
ll yl = -1e18;
ll yr = 1e18;
ll m1, m2;
bool done = 0;
while(true){
m1 = (xl + xr)/2;
m2 = (yl + yr)/2;
query1(m1,m2);
string ans;
cin>>ans;
if(ans == "O"){
done = 1;
break;
}
if(ans[0] == 'X'){
xl = m1;
xr = m1;
}
if(ans[0] == 'P'){
xr = m1-1;
}
if(ans[0] == 'N'){
xl = m1+1;
}
if(ans[1] == 'Y'){
yl = m2;
yr = m2;
}
if(ans[1] == 'P'){
yr = m2-1;
}
if(ans[1] == 'N'){
yl = m2+1;
}
if(d == 1){
xl--;
xr++;
yl--;
yr++;
}
if(d == 1 && max(xr-xl, yr-yl) <= 3) break;
}
if(d == 0) continue;
if(done) continue;
// d == 1, square of side atmost 4
if(max(xr-xl, yr-yl) == 2){
solve33(xl, xr, yl, yr);
}
else{
if(min(xr-xl, yr-yl) == 2){
solve34(xl, xr, yl, yr);
}
else solve44(xl, xr, yl, yr);
}
}
return 0;
}
As always, doubts and alternative solutions are welcome.
