v. Interactive Problems

In an interactive problem your program talks to a judge program. The query limit is part of the statement, and it is the strongest hint about the intended algorithm.

The rules

1. Flush after every line. Use endl, cout << flush, or fflush(stdout). A forgotten flush gives Idleness Limit Exceeded.
2. Don’t untie cin from cout unless you flush manually every time. The tie is what makes cin flush pending output.
3. Stop on $-1$. After an invalid or excessive query most judges reply $-1$. Exit immediately, or the verdict turns into Idleness/RE and hides the real WA.
4. Exceeding the query budget is WA, not TLE.

int ask(int l, int r) {
    cout << "? " << l << ' ' << r << endl;
    int x; cin >> x;
    if (x == -1) exit(0);
    return x;
}
void answer(int x) { cout << "! " << x << endl; }

Budget to technique

Budget	Technique
$\lceil {\log }_{2}n\rceil$	binary search; decision-tree lower bound is tight
$\lceil {\log }_{3}n\rceil$	three-way splits (balance scales: each weighing has 3 outcomes)
$2\lceil {\log }_{2}n\rceil$	binary search plus verification, or two independent searches
${\log }^{2}n$	nested binary search, binary search on a tree or on HLD chains
$n+O(\log n)$	one pass, then a binary search; tournament for the second maximum ($n+\lceil \log n\rceil -2$ comparisons)
$\lceil 3n/2\rceil -2$	min and max together: compare in pairs

Proof: the tournament finds the second maximum in $n+\lceil \log n\rceil -2$ comparisons

Run a single-elimination tournament: pair up elements, keep the larger, repeat — this is a binary tree with $n$ leaves and $n-1$ internal nodes (comparisons), found by induction: a tree on 1 leaf needs 0 comparisons, and merging two trees on $p,q$ leaves with $p-1,q-1$ comparisons needs one more comparison between their winners, giving $(p-1)+(q-1)+1=(p+q)-1$. So the overall maximum costs $n-1$ comparisons, and the tree has depth $\lceil {\log }_{2}n\rceil$, so the max played (and won) exactly $\lceil {\log }_{2}n\rceil$ matches on its path to the root, each against a distinct opponent — call this set $S$, $|S|=\lceil {\log }_{2}n\rceil$. The second-largest element $x$ is not the max, so it lost at least one match, say to $y$. Since $x$ is second-largest, the only element larger than $x$ is the max itself, so $y$ (being larger than $x$) must be the max. Hence $x\in S$ — every candidate for second place lost directly to the max. Finding the largest of the (at most) $\lceil {\log }_{2}n\rceil$ elements in $S$ by the same tournament argument costs $\lceil {\log }_{2}n\rceil -1$ more comparisons, for a total of $(n-1)+(\lceil {\log }_{2}n\rceil -1)=n+\lceil {\log }_{2}n\rceil -2$. $■$

Proof: pairwise comparison finds min and max together in $\lceil 3n/2\rceil -2$ comparisons

Process elements two at a time: compare each pair (1 comparison) to get a local min/max, then compare the local min against the running global min and the local max against the running global max (2 more comparisons) — 3 comparisons per pair, except the very first pair, where the local min/max comparison is the initial global min/max, so no extra 2 comparisons are needed there. With $n$ even: 1 pairing comparison for the first pair plus $(n/2-1)$ triples of 3 for the rest $=1+3(n/2-1)=3n/2-2$. With $n$ odd, seed the global min/max with the first single element (0 comparisons) and process the remaining $n-1$ (even) elements in pairs at 3 comparisons each: $3(n-1)/2=(3n-3)/2$, which equals $\lceil 3n/2\rceil -2$ for odd $n$ (check: $\lceil 3n/2\rceil =(3n+1)/2$ for odd $n$, so $\lceil 3n/2\rceil -2=(3n-3)/2$, matching). This is a known tight bound (Knuth, TAOCP Vol. 3) — no comparison-based strategy does better; the matching adversary lower bound is a standard but longer argument, not reproduced here. $■$
| $n\log n$ | sorting with a comparison oracle (stable_sort with the query as the comparator, or merge sort to bound comparisons) |
| $O(\sqrt{n})$ | block decomposition, baby-step giant-step |
| $n/2+O(1)$ | pairing arguments |
| $O(1)$ | algebraic identity (sums, XORs, symmetric functions) |

Information-theoretic lower bound: with $k$ possible replies per query and $N$ possible hidden answers you need at least $\lceil {\log }_{k}N\rceil$ queries. If the budget equals that, every query must split the candidate set evenly.

Proof: the $\lceil {\log }_{k}N\rceil$ query lower bound

Model the interaction as a $k$-ary decision tree: each internal node is one query, each of its $k$ children is one possible reply, and each leaf is a hidden answer the strategy can still distinguish. The strategy must end at a distinct leaf for each of the $N$ possible hidden answers (otherwise two different answers would receive the same final guess), so the tree needs at least $N$ leaves. A $k$-ary tree of depth $d$ has at most $k^d$ leaves, so $k^d\ge N$, giving $d\ge {\log }_{k}N$, and since $d$ is an integer, $d\ge \lceil {\log }_{k}N\rceil$. The depth is exactly the worst-case number of queries, so no strategy beats this bound. When the budget is exactly $\lceil {\log }_{k}N\rceil$, equality forces every internal node to have (close to) $k^{d-1}$ leaves in each subtree, i.e. every query must split the remaining candidates as evenly as possible — an uneven split would make the larger branch need more than the remaining budget. $■$

Adaptive judges

An adaptive interactor doesn’t fix the hidden answer in advance. It keeps every answer consistent with your queries so far and picks the one that hurts you most. Consequences:

• “Works on average” is not enough. Every query must guarantee progress in the worst case (an adversary argument).
• Randomised strategies still work against a judge that can’t see your random bits, as long as the bound holds in expectation for every fixed hidden answer. But if the statement says “adaptive”, assume the worst case.
• Ternary-style elimination needs care: guarantee that the candidate set shrinks by a constant factor for every possible reply.

Classic patterns

• Binary search on an unknown monotone predicate. Find the first “yes” in $[1,n]$.
• Binary search with a lying oracle. With at most $k$ lies, repeat each query $2k+1$ times and take the majority. Optimal strategies are Ulam’s game or Berlekamp’s volume bound.

Proof: majority of $2k+1$ repeats is correct against at most $k$ lies

Repeating one query $2k+1$ times gives $2k+1$ replies, and the oracle can mark at most $k$ of them as lies (by hypothesis, across the whole interaction, so certainly within this one batch of repeats). So at least $(2k+1)-k=k+1$ of the replies are truthful, and truthful replies to the same query all agree (the question has one correct answer), so the truthful answer appears at least $k+1$ times. Any other (lying) answer appears at most $k$ times in total across all repeats, hence strictly fewer than $k+1$. So the truthful answer is a strict majority among the $2k+1$ replies, and taking the majority recovers it correctly. $■$

• Finding a hidden permutation with $O(n\log n)$ comparisons: insertion with binary search, or merge sort.
• Peak or local minimum in an array or grid with $O(\log n)$ or $O(n)$ queries: walk downhill on a recursively halved window.
• Guessing with XOR, AND or OR queries: recover each bit independently. $\mathrm{a}+\mathrm{b}=(a\oplus b)+2(a\&b)$ turns two queries into sums.
• Tree centroid search: query the centroid of the remaining candidates, so the candidate count halves each time and $\lceil {\log }_{2}n\rceil$ queries suffice.
• Hidden graph edges: group testing, binary search on prefix sets of vertices (“is there an edge from $v$ into $S$?”).

Testing locally

Put a fake interactor in your own code behind #ifdef LOCAL. That tests the logic without any process plumbing:

#ifdef LOCAL
int hidden, used = 0;
int ask(int x) { assert(++used <= LIMIT); return x <= hidden; }
#else
int ask(int x) { cout << "? " << x << endl; int r; cin >> r; if (r == -1) exit(0); return r; }
#endif

Stress the fake interactor over many hidden values, including adversarial ones. For a real two-process test: mkfifo f; ./sol < f | ./interactor > f.

Symptom	Cause
Idleness limit	no flush
WA immediately	wrong format (?/! prefixes, spaces, 0- vs 1-based)
WA late	over budget, or off-by-one in the bounds
RE	kept reading after $-1$
Passes locally, fails on the judge	your local interactor isn’t adaptive