# Codejam 2020 Round B Problem 2

``````#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

string query(ll x,ll y)
{
cout << x << " " << y << endl;
cout.flush();
string s;
cin >> s;
return s;
}

void solve()
{

ll  req_x, req_y , flag = 0;

for(ll i=-1 ; i<=1 ; ++i)
{
for(ll j=-1 ; j<=1 ; ++j)
{
ll x = i*( (ll)1e9/2 );
ll y = j*( (ll)1e9/2 );

string q = query(x,y);

if(q == "HIT")
{
req_x = x , req_y = y;
flag = 1;
break;
}

if(q == "CENTER")
return;
}

if(flag) break;
}

ll left_x , right_x , upper_y , lower_y;

ll lower = (ll)-1e9 , upper = req_x;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( mid , req_y);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" )
upper = mid;
else if( q == "CENTER" )
return;
}
left_x = lower;

lower = req_x , upper = (ll)1e9;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( mid , req_y);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" )
lower = mid;
else if( q == "CENTER" )
return;
}
right_x = lower;

lower = (ll)-1e9 , upper = req_y;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( req_x , mid);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" )
upper = mid;
else if( q == "CENTER" )
return;
}
lower_y = lower;

lower = req_y , upper = (ll)1e9;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( req_x , mid);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" )
lower = mid;
else if( q == "CENTER" )
return;
}
upper_y = lower;

string q = query( (left_x+right_x)/2 , (lower_y+upper_y)/2 );
return;

}

int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ll t,a,b;
cin >> t >> a >> b;

while(t--)
{
solve();
}

return 0;
}
``````

When I try to run this using the local testing tool, It says Judge couldnâ€™t read valid line?
Any idea where am I going wrong?

Remove `cout.tie()`

I used `cout.tie()` in the qualifying round interactive problem , it worked fine.

@everule1, I was able to fix this error, but now I am not able to find the center in 300 queries. I think my logic is flawed but I canâ€™t seem to find the error. Can you help.

``````#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

bool wrong = false;
ll cnt = 0;

string query(ll x,ll y)
{
cout << x << " " << y << endl;
cout.flush();
string s;
cin >> s;
cnt++;
if(s == "WRONG" || cnt >= 300)
{
s = "WRONG";
wrong = true;
}
return s;
}

void solve()
{

ll  req_x, req_y;

for(ll i=-4 ; i<=4 ; ++i)
{
for(ll j=-4 ; j<=4 ; ++j)
{
ll x = i*( (ll)1e9/4 );
ll y = j*( (ll)1e9/4 );

string q = query(x,y);

if(q == "HIT")
{
req_x = x , req_y = y;
}

if(q == "CENTER")
return;
}
}

ll left_x , right_x , upper_y , lower_y;

ll lower = (ll)-1e9 , upper = req_x;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( mid , req_y);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" )
upper = mid;
else if( q == "CENTER" )
return;
else return;
}
left_x = lower;

lower = req_x , upper = (ll)1e9;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( mid , req_y);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" )
lower = mid;
else if( q == "CENTER" )
return;
else return;
}
right_x = lower;

lower = (ll)-1e9 , upper = req_y;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( req_x , mid);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" )
upper = mid;
else if( q == "CENTER" )
return;
else return;
}
lower_y = lower;

lower = req_y , upper = (ll)1e9;
while(lower < upper)
{
ll mid  = (lower+upper)/2;
string q = query( req_x , mid);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" )
lower = mid;
else if( q == "CENTER" )
return;
else return;
}
upper_y = lower;

string q = query( (left_x+right_x)/2 , (lower_y+upper_y)/2 );
return;

}

int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ll t,a,b;
cin >> t >> a >> b;

while(t--)
{
cnt = 0;
solve();
if(wrong) return -1;
}

return 0;
}
``````
``````string q = query( (left_x+right_x)/2 , (lower_y+upper_y)/2 );
``````

My guess is that this is the problem. You arenâ€™t given exact co-ordinates. I would check points close to this as well. at least an error term of 3.

I am binary searching for symmetrical end points so I am quite sure there wonâ€™t be any error.

But there is. A circleâ€™s edges arenâ€™t on lattice points.

Can you give a geometrical example? I think symmetry takes care of that as center lies on a lattice point.

Youâ€™re right.
Instead of trying to just read your code, I ran it locally to figure out whatâ€™s wrong, and all your binary searches seem to get stuck.
This is your output for a random test case.
The last line is X, Y and R respectively

``````-1000000000 -1000000000
MISS
-1000000000 -750000000
MISS
-1000000000 -500000000
MISS
-1000000000 -250000000
MISS
-1000000000 0
MISS
-1000000000 250000000
MISS
-1000000000 500000000
MISS
-1000000000 750000000
MISS
-1000000000 1000000000
MISS
-750000000 -1000000000
MISS
-750000000 -750000000
MISS
-750000000 -500000000
MISS
-750000000 -250000000
MISS
-750000000 0
MISS
-750000000 250000000
MISS
-750000000 500000000
MISS
-750000000 750000000
MISS
-750000000 1000000000
MISS
-500000000 -1000000000
MISS
-500000000 -750000000
MISS
-500000000 -500000000
MISS
-500000000 -250000000
MISS
-500000000 0
HIT
-500000000 250000000
MISS
-500000000 500000000
MISS
-500000000 750000000
MISS
-500000000 1000000000
MISS
-250000000 -1000000000
MISS
-250000000 -750000000
MISS
-250000000 -500000000
MISS
-250000000 -250000000
HIT
-250000000 0
HIT
-250000000 250000000
HIT
-250000000 500000000
MISS
-250000000 750000000
MISS
-250000000 1000000000
MISS
0 -1000000000
MISS
0 -750000000
MISS
0 -500000000
MISS
0 -250000000
HIT
0 0
HIT
0 250000000
HIT
0 500000000
HIT
0 750000000
MISS
0 1000000000
MISS
250000000 -1000000000
MISS
250000000 -750000000
MISS
250000000 -500000000
MISS
250000000 -250000000
HIT
250000000 0
HIT
250000000 250000000
HIT
250000000 500000000
MISS
250000000 750000000
MISS
250000000 1000000000
MISS
500000000 -1000000000
MISS
500000000 -750000000
MISS
500000000 -500000000
MISS
500000000 -250000000
MISS
500000000 0
MISS
500000000 250000000
MISS
500000000 500000000
MISS
500000000 750000000
MISS
500000000 1000000000
MISS
750000000 -1000000000
MISS
750000000 -750000000
MISS
750000000 -500000000
MISS
750000000 -250000000
MISS
750000000 0
MISS
750000000 250000000
MISS
750000000 500000000
MISS
750000000 750000000
MISS
750000000 1000000000
MISS
1000000000 -1000000000
MISS
1000000000 -750000000
MISS
1000000000 -500000000
MISS
1000000000 -250000000
MISS
1000000000 0
MISS
1000000000 250000000
MISS
1000000000 500000000
MISS
1000000000 750000000
MISS
1000000000 1000000000
MISS
-375000000 250000000
HIT
-687500000 250000000
MISS
-531249999 250000000
MISS
-453124999 250000000
MISS
-414062499 250000000
HIT
-433593748 250000000
MISS
-423828123 250000000
HIT
-428710935 250000000
HIT
-431152341 250000000
HIT
-432373044 250000000
HIT
-432983395 250000000
HIT
-433288571 250000000
MISS
-433135982 250000000
MISS
-433059688 250000000
HIT
-433097834 250000000
MISS
-433078760 250000000
MISS
-433069223 250000000
MISS
-433064455 250000000
HIT
-433066838 250000000
MISS
-433065646 250000000
MISS
-433065050 250000000
MISS
-433064752 250000000
MISS
-433064603 250000000
MISS
-433064528 250000000
HIT
-433064565 250000000
MISS
-433064546 250000000
MISS
-433064536 250000000
HIT
-433064540 250000000
HIT
-433064542 250000000
HIT
-433064543 250000000
MISS
625000000 250000000
MISS
437499999 250000000
MISS
343749999 250000000
HIT
390624998 250000000
HIT
414062498 250000000
HIT
425781248 250000000
HIT
431640623 250000000
HIT
434570310 250000000
MISS
433105466 250000000
MISS
432373044 250000000
HIT
432739254 250000000
HIT
432922359 250000000
HIT
433013912 250000000
HIT
433059688 250000000
MISS
433036799 250000000
MISS
433025355 250000000
HIT
433031076 250000000
MISS
433028215 250000000
MISS
433026784 250000000
MISS
433026069 250000000
HIT
433026426 250000000
MISS
433026247 250000000
MISS
433026157 250000000
MISS
433026112 250000000
HIT
433026134 250000000
HIT
433026145 250000000
MISS
433026139 250000000
HIT
433026141 250000000
HIT
433026142 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
433026143 250000000
HIT
WRONG
-19199 20251 500018144
``````
Corrected code

I left in the preprocessor directives so you can see how I checked your code.

``````#include <bits/stdc++.h>
using namespace std;
//#define local
typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

bool wrong = false;
ll cnt = 0;
#ifdef local
struct Judge{
ll R;
ll X,Y;
int queries;
void create(int a, int b){
R=rand()%(b-a) + a;
queries=0;
X=rand()%(int(1e9) - R);
Y=rand()%(int(1e9) - R);
if(rand()%2){
X=-X;
}
if(rand()%2){
Y=-Y;
}
}
if(queries>=300){
return "WRONG";
}
++queries;
if(X==x && Y==y){
return "CENTER";
}
if(llabs(X-x)*llabs(X-x) + llabs(Y-y)*llabs(Y-y) <= R*R){
return "HIT";
}
else{
return "MISS";
}
}
void print(){
cout<<X<<" "<<Y<<" "<<R<<"\n";
}
};
Judge judge;
#endif
string query(ll x,ll y)
{
cout<<x<<" "<<y<<"\n";
#ifdef local
cout<<s<<"\n";
#else
cout.flush();
string s;
cin>>s;
#endif
cnt++;
if(s == "WRONG" || cnt >= 300)
{
s = "WRONG";
wrong = true;
}
return s;
}
void solve()
{

ll  req_x, req_y;

for(ll i=-4 ; i<=4 ; ++i)
{
for(ll j=-4 ; j<=4 ; ++j)
{
ll x = i*( (ll)1e9/4 );
ll y = j*( (ll)1e9/4 );

string q = query(x,y);

if(q == "HIT")
{
req_x = x , req_y = y;
}

if(q == "CENTER")
return;
}
}

ll left_x , right_x , upper_y , lower_y;

ll lower = (ll)-1e9 , upper = req_x;
while(lower < upper)
{
ll mid  = (lower+upper -1)/2;
string q = query( mid , req_y);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" )
upper = mid;
else if( q == "CENTER" )
return;
else return;
}
left_x = lower;

lower = req_x , upper = (ll)1e9;
while(lower < upper)
{
ll mid  = (lower+upper+1)/2;
string q = query( mid , req_y);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" )
lower = mid;
else if( q == "CENTER" )
return;
else return;
}
right_x = lower;

lower = (ll)-1e9 , upper = req_y;
while(lower < upper)
{
ll mid  = (lower+upper - 1)/2;
string q = query( req_x , mid);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" )
upper = mid;
else if( q == "CENTER" )
return;
else return;
}
lower_y = lower;

lower = req_y , upper = (ll)1e9;
while(lower < upper)
{
ll mid  = (lower+upper + 1)/2;
string q = query( req_x , mid);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" )
lower = mid;
else if( q == "CENTER" )
return;
else return;
}
upper_y = lower;

string q = query( (left_x+right_x)/2 , (lower_y+upper_y)/2 );
return;

}

int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ll t,a,b;
cin >> t;
#ifdef local
a=5e8, b=1e9;
#else
cin>>a>>b;
#endif
srand(time(0));
while(t--)
{
#ifdef local
judge.create(a, b);
#endif
cnt = 0;
solve();
#ifdef local
if(wrong){
cout<<"WRONG"<<"\n";
judge.print();
}
#else
if(wrong){
return -1;
}
#endif
}

return 0;
}
``````

There was an isssue in your binary search, I have modified the code it is passing all the test cases. I have also decreased the counts in loop to further reduce queries (it is not required, just an improvisation).

``````#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

bool wrong = false;
ll cnt = 0;

string query(ll x,ll y)
{
cout << x << " " << y << endl;
cout.flush();
string s;
cin >> s;
cnt++;
if(s == "WRONG" || cnt >= 300)
{
s = "WRONG";
wrong = true;
}
return s;
}

void solve()
{

ll  req_x, req_y;

for(ll i=-2 ; i<=2 ; ++i)
{
for(ll j=-2 ; j<=2 ; ++j)
{
ll x = i*( (ll)1e9/2 );
ll y = j*( (ll)1e9/2 );

string q = query(x,y);

if(q == "HIT")
{
req_x = x , req_y = y;
}

if(q == "CENTER")
return;
}
}

ll left_x , right_x , upper_y , lower_y, p1, p2, p3, p4;

ll lower = (ll)-1e9 , upper = req_x;
while(lower <= upper)
{
ll mid  = (lower+upper)/2;
string q = query( mid , req_y);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" ) {
upper = mid-1;
p1 = mid;
}
else if( q == "CENTER" )
return;
else return;
}

lower = req_x , upper = (ll)1e9;
while(lower <= upper)
{
ll mid  = (lower+upper)/2;
string q = query( mid , req_y);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" ) {
lower = mid+1;
p2 = mid;
}
else if( q == "CENTER" )
return;
else return;
}

lower = (ll)-1e9 , upper = req_y;
while(lower <= upper)
{
ll mid  = (lower+upper)/2;
string q = query( req_x , mid);
if( q == "MISS" )
lower = mid+1;
else if( q == "HIT" ) {
upper = mid-1;
p3 = mid;
}
else if( q == "CENTER" )
return;
else return;
}

lower = req_y , upper = (ll)1e9;
while(lower <= upper)
{
ll mid  = (lower+upper)/2;
string q = query( req_x , mid);
if( q == "MISS" )
upper = mid-1;
else if( q == "HIT" ) {
lower = mid+1;
p4 = mid;
}
else if( q == "CENTER" )
return;
else return;
}

string q = query( (p1+p2)/2 , (p3+p4)/2 );
return;

}

int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ll t,a,b;
cin >> t >> a >> b;

while(t--)
{
cnt = 0;
solve();
if(wrong) return -1;
}

return 0;
}``````

This was really insightful, thanks a lot (a lot!). Any idea why my binary searches got stuck ?

say low was 3 and high was 4, in binary search 2.
You would ask 3+4/2 = 3, and set low to 3. You would just keep on doing that.

Try, lower = -3, upper=-2. You will get the idea why it got stuck.

I was trying to debug the first binary search all this time lol. Got it thanks. Just used ceil(mid) in 2nd and 4th Binary search got ACâ€™d.

I had no problem in Quali this year, but 1B had the same problem (on win10 pc) that I had some years before with the interactive runner: although my â€śpythonâ€ť is configured to default to python 3, the python for my code was complaining with the differences (e.g. input-raw_input). I was not able to rewrite the full code but was really annoying having no test possibilities (as the numbers are huge so I couldnâ€™t interactively provide the answers by hand).
Did anyone encountered the same? And more importantly, any idea how to avoid this next time?(python2 is required by another program so no complete uninstall possible)

Axioma

You can create a virtual environment with required python version as default and run interactive runner in it.

Hey, can you let me know how you fixed the â€śCouldnâ€™t read a valid lineâ€ť error ?

I had defined IO flags in my sublime build file. Just remove them or compile the code manually.

Yes, I have been compiling the code manually but even this simple cout in the code is giving the â€śCouldnâ€™t read a valid lineâ€ť error.

#include <bits/stdc++.h>
using namespace std;

int main() {
int t,a,b; cin >> t >> a >> b;
while(tâ€“) {
int x = 5000 , y = 5000 ;
cout << x << â€™ â€™ << y << endl;
break ;
}
return 0;
}

This works, fine. Problem is judge is waiting for your queries but your program terminates before that.

``````#include <bits/stdc++.h>
using namespace std;

int main() {
int t,a,b; cin >> t >> a >> b;
while(t--)
{
for(int i=0 ; i<501  ; ++i)
{
int x = 5000 , y = 5000 ;
cout << x << " " << y << "\n";
cout.flush();
}
break ;
}
return 0;
}
``````