IOI 2007 - Aliens

#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;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{geometry}
\usepackage{hyperref}
\geometry{margin=2.5cm}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\bfseries,
  breaklines=true,
  frame=single,
  numbers=left,
  numberstyle=\tiny,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2007 -- Aliens}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}
This is an \textbf{interactive problem}. There is an $N \times N$ grid with a single hidden target cell. You may issue queries of the form \texttt{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.

\section{Solution}

\subsection{Simultaneous 2D Binary Search}
Each query at $(x, y)$ reveals the quadrant containing the target, which narrows the search space in \emph{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:
\begin{enumerate}
    \item Query the center $\bigl(\lfloor(lo_x + hi_x)/2\rfloor,\; \lfloor(lo_y + hi_y)/2\rfloor\bigr)$.
    \item Based on the response, update the bounding box:
    \begin{itemize}
        \item NE: $lo_x \gets mx + 1$, $lo_y \gets my + 1$.
        \item NW: $hi_x \gets mx - 1$, $lo_y \gets my + 1$.
        \item SW: $hi_x \gets mx - 1$, $hi_y \gets my - 1$.
        \item SE: $lo_x \gets mx + 1$, $hi_y \gets my - 1$.
    \end{itemize}
\end{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.

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Queries:} $O(\log N)$.
    \item \textbf{Space:} $O(1)$.
\end{itemize}

\section{C++ Solution}

\begin{lstlisting}
#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
}
\end{lstlisting}

\section{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.

\end{document}