Aliens
Simultaneous 2D Binary Search Each query at (x, y) reveals the quadrant containing the target, which narrows the search space in both dimensions simultaneously. Maintain a bounding box [lo_x, hi_x] [lo_y, hi_y], initi...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
This is an interactive problem. There is an $N \times N$ grid with a single hidden target cell. You may issue queries of the form examine$(x, y)$, and the grader responds with the quadrant of the target relative to $(x, y)$: NE, NW, SW, SE, or ``found'' if $(x,y)$ is the target. Determine the target cell using at most $O(\log N)$ queries.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Simultaneous 2D Binary Search
Each query at $(x, y)$ reveals the quadrant containing the target, which narrows the search space in both dimensions simultaneously.
Maintain a bounding box $[lo_x, hi_x] \times [lo_y, hi_y]$, initially $[1, N] \times [1, N]$. At each step:
Query the center $\bigl(\lfloor(lo_x + hi_x)/2\rfloor,\; \lfloor(lo_y + hi_y)/2\rfloor\bigr)$.
Based on the response, update the bounding box:
NE: $lo_x \gets mx + 1$, $lo_y \gets my + 1$.
NW: $hi_x \gets mx - 1$, $lo_y \gets my + 1$.
SW: $hi_x \gets mx - 1$, $hi_y \gets my - 1$.
SE: $lo_x \gets mx + 1$, $hi_y \gets my - 1$.
enumerate Each query halves (at least) one dimension, so the box area shrinks by a factor of at least 2. After at most $2\lceil\log_2 N\rceil$ queries the box is a single cell.
Complexity
Queries: $O(\log N)$.
Space: $O(1)$.
C++ Solution
#include <bits/stdc++.h> using namespace std; // Grader-provided function. // Returns 0 (found), 1 (NE), 2 (NW), 3 (SW), 4 (SE). int examine(int x, int y); void solve(int N) { int lo_x = 1, hi_x = N; int lo_y = 1, hi_y = N; while (lo_x <= hi_x && lo_y <= hi_y) { int mx = (lo_x + hi_x) / 2; int my = (lo_y + hi_y) / 2; int res = examine(mx, my); if (res == 0) return; // found if (res == 1) { lo_x = mx + 1; lo_y = my + 1; } // NE if (res == 2) { hi_x = mx - 1; lo_y = my + 1; } // NW if (res == 3) { hi_x = mx - 1; hi_y = my - 1; } // SW if (res == 4) { lo_x = mx + 1; hi_y = my - 1; } // SE } examine(lo_x, lo_y); // final verification }Notes
The quadrant feedback eliminates at least three-quarters of the remaining search area at each step, giving $O(\log N)$ queries. Edge cases arise when the target shares a row or column with the query point; the exact response encoding in the grader determines which boundary to include or exclude. The solution above assumes strict inequalities in the grader responses.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// Interactive: examine(x, y) returns:
// 0 if (x, y) is the target
// 1 if target is to the upper-right
// 2 if target is to the upper-left
// 3 if target is to the lower-left
// 4 if target is to the lower-right
// (exact encoding depends on problem statement)
// Forward declaration for grader function
int examine(int x, int y);
void solve(int N) {
// Binary search on x and y simultaneously
int lo_x = 1, hi_x = N;
int lo_y = 1, hi_y = N;
while (lo_x < hi_x || lo_y < hi_y) {
int mx = (lo_x + hi_x) / 2;
int my = (lo_y + hi_y) / 2;
int res = examine(mx, my);
if (res == 0) return; // found!
// Adjust based on response
// Response encoding (example):
// "NE" (1): target is north and east -> x > mx, y > my
// "NW" (2): target is north and west -> x < mx, y > my
// "SW" (3): target is south and west -> x < mx, y < my
// "SE" (4): target is south and east -> x > mx, y < my
if (res == 1) { // NE
lo_x = mx + 1;
lo_y = my + 1;
} else if (res == 2) { // NW
hi_x = mx - 1;
lo_y = my + 1;
} else if (res == 3) { // SW
hi_x = mx - 1;
hi_y = my - 1;
} else if (res == 4) { // SE
lo_x = mx + 1;
hi_y = my - 1;
}
}
examine(lo_x, lo_y); // final check
}
// For non-interactive testing:
int target_x, target_y;
int examine(int x, int y) {
if (x == target_x && y == target_y) return 0;
int res = 0;
if (target_x > x && target_y > y) res = 1;
else if (target_x < x && target_y > y) res = 2;
else if (target_x < x && target_y < y) res = 3;
else res = 4;
return res;
}
int main(){
int N;
cin >> N >> target_x >> target_y;
solve(N);
cout << target_x << " " << target_y << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.