Hotter Colder

An interactive problem on the integer line [1, N]. A hidden value X is fixed. Starting from position 1, each guess G receives a response: Hotter (+1): |G - X| < |P - X| where P is the previous guess. Colder (-1): |G -...

Updated May 21, 2026

Track IOI

Year 2010

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Summary" section in the LaTeX write-up.

Open TeX section

An interactive problem on the integer line $[1, N]$. A hidden value $X$ is fixed. Starting from position $1$, each guess $G$ receives a response:

Hotter ($+1$): $|G - X| < |P - X|$ where $P$ is the previous guess.
Colder ($-1$): $|G - X| > |P - X|$.
Same ($0$): $|G - X| = |P - X|$.
Find $X$ using at most $\lceil \log_2 N \rceil + 1$ queries.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution

Key Observation

If the previous guess is $P$ and the new guess is $G$, the perpendicular bisector of $P$ and $G$ is at position $M = (P + G) / 2$. The response partitions the line:

Hotter: $X$ is on the same side of $M$ as $G$.
Colder: $X$ is on the same side of $M$ as $P$.
Same: $X = M$ (only possible when $P + G$ is even).

Algorithm

Maintain a feasible interval $[\mathit{lo}, \mathit{hi}]$ for $X$, initially $[1, N]$. At each step:

Compute the midpoint $\mathit{mid} = \lfloor (\mathit{lo} + \mathit{hi}) / 2 \rfloor$.
Choose $G = 2 \cdot \mathit{mid} + 1 - P$ so that the bisector of $P$ and $G$ falls at $\mathit{mid} + 0.5$ (between $\mathit{mid}$ and $\mathit{mid}+1$). Clamp $G$ to $[1, N]$.
If Hotter and $G > P$: set $\mathit{lo} = \mathit{mid} + 1$.
If Hotter and $G < P$: set $\mathit{hi} = \mathit{mid}$.
Colder is symmetric.
If Same: $X = (P + G) / 2$ (return immediately).
Update $P \leftarrow G$.

Correctness and Query Bound

Theorem.

The algorithm finds $X$ in at most $\lceil \log_2 N \rceil + 1$ queries.

Proof.

After the first query, we have $P \neq 1$ in general, and the feasible interval has been halved. Each subsequent query halves the interval, requiring $\lceil \log_2 N \rceil$ halvings. Adding the initial positioning query gives at most $\lceil \log_2 N \rceil + 1$ total queries.

Complexity

Queries: $O(\log N)$.
Time and space: $O(1)$.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 2010 - Hotter Colder (Interactive)
// Binary search on hidden position using distance comparisons.
// O(log N) queries.
#include <bits/stdc++.h>
using namespace std;

// Grader-provided: returns 1 (hotter), -1 (colder), 0 (same distance).
int Guess(int G);

int HC(int N) {
    int lo = 1, hi = N;
    int prev = 1; // starting position

    while (lo < hi) {
        int mid = (lo + hi) / 2;
        // Choose G so that the midpoint of (prev, G) splits [lo, hi].
        int G;
        if (prev <= mid) {
            G = 2 * mid + 1 - prev;
        } else {
            G = 2 * mid - prev;
        }
        G = max(1, min(N, G));

        int result = Guess(G);

        if (result == 0) {
            return (prev + G) / 2;
        }

        int boundary = (prev + G) / 2;
        if (result == 1) {
            // X is closer to G: on G's side of boundary.
            if (G > prev) lo = boundary + 1;
            else          hi = boundary;
        } else {
            // X is closer to prev: on prev's side of boundary.
            if (G > prev) hi = boundary;
            else          lo = boundary + 1;
        }

        prev = G;
    }

    return lo;
}

// Stub main for standalone compilation.
int main() {
    int N;
    cin >> N;
    cout << HC(N) << endl;
    return 0;
}

int Guess(int /*G*/) { return 0; }

Show raw files

TeX write-upcompetitive_programming/ioi/2010/hottercolder/solution.texC++ implementationcompetitive_programming/ioi/2010/hottercolder/solution.cpp