Interactive Problems

Quick Revisit

• USE WHEN: The problem says "Interaction"—your program queries a judge and adapts based on responses
• INVARIANT: Each query must maximally reduce the search space; total queries ≤ budget (usually ⌈log₂ n⌉)
• TIME: O(log n) queries typical (binary-search style) | SPACE: O(1)–O(n) depending on problem
• CLASSIC BUG: Forgetting to flush output (cout << endl or fflush(stdout))—causes deadlock, not WA
• PRACTICE: 01-ladder-1100-to-1400

Your program and the judge talk in real time: you print a query, flush, and act on the response—repeating until you identify the hidden answer. Every interactive problem is a decision tree, and every query buys you information. Spend each one wisely, and always flush.

Difficulty: Beginner | Prerequisites: Binary Search | CF Rating Range: 1100–1900

---

Contents

• Intuition
• Visual Intuition (Protocol Diagram)
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Deeper Insights & Tactics
• Further Reading

---

Intuition

You are given a hidden number $x$ where $1\le x\le 1000$. You can ask up to 10 queries. Each query prints a number $g$; the judge replies "higher", "lower", or "correct". Find $x$.

Binary search—easy, right? $\lceil {\log }_{2}1000\rceil =10$ queries suffice. You write this:

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

int main() {
    int lo = 1, hi = 1000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        cout << mid;          // <-- BUG: no newline, no flush
        string resp;
        cin >> resp;           // hangs forever
        if (resp == "higher") lo = mid + 1;
        else if (resp == "lower") hi = mid - 1;
        else break;
    }
    cout << lo;
    return 0;
}

You submit. Time Limit Exceeded. The program printed 500 but the judge never saw it—the output is sitting in a buffer. Your program waits for a response; the judge waits for your query. Deadlock.

The logic is correct. The I/O kills you. This is the #1 reason people fail their first interactive problem.

"Interactive problems are decision trees—at each step, pick the query that maximally reduces the remaining search space. And always, always flush your output after every query."

  Decision Tree for Guessing x in [1, 8]:

              Query 4
             /       \
          "lower"   "higher"
           /           \
       [1..3]        [5..8]
       Query 2       Query 6
       /    \         /    \
    [1] [3]        [5]   [7..8]
     |   Query 3    |    Query 7
     *   /   \      *    /    \
       [3]   *        [7]    [8]
        *               *      *

  Depth = ceil(log2(8)) = 3 queries max
  Every leaf is reached in at most 3 steps

Now scale up. With $N=16$ and a budget of $\lceil {\log }_{2}16\rceil =4$ queries, the full binary search decision tree looks like this:

  Hidden x in [1, 16], budget = 4 queries

                         Query: 8
                        /        \
                  "lower"        "higher"
                   /                    \
              [1..8]                  [9..16]
             Query: 4                Query: 12
             /      \                /       \
         [1..4]   [5..8]       [9..12]   [13..16]
         Query:2  Query:6      Query:10  Query:14
          / \      / \           / \       / \
      [1,2][3,4][5,6][7,8]  [9,10][11,12][13,14][15,16]

  Level 4 -- final query resolves each pair:
  [1,2]   -> Query:1  -> {1}  or {2}
  [3,4]   -> Query:3  -> {3}  or {4}
  [5,6]   -> Query:5  -> {5}  or {6}
  [7,8]   -> Query:7  -> {7}  or {8}
  [9,10]  -> Query:9  -> {9}  or {10}
  [11,12] -> Query:11 -> {11} or {12}
  [13,14] -> Query:13 -> {13} or {14}
  [15,16] -> Query:15 -> {15} or {16}

  Every leaf reached in exactly 4 queries.  2^4 = 16 >= N.

The tree is perfectly balanced: every path from root to leaf has exactly 4 edges. This is the best possible—no strategy can do better against a worst-case (or adaptive) judge because each yes/no response carries at most 1 bit of information, and ${\log }_{2}16=4$ bits are needed to identify one element out of 16.

Think of the 20-questions game: each question should cut the remaining candidates in half, and you keep asking until only one possibility remains. But if you whisper too quietly for the other player to hear (no flush), the game freezes mid-sentence. The analogy maps almost perfectly—your program is the guesser, the judge is the answerer, and flushing is simply speaking loudly enough to be heard.

Where it breaks down: in real 20-questions the answerer is honest. In some interactive problems the judge is adaptive—it picks answers that maximally hurt your strategy. More on that later.

Visual Walkthrough

Hidden number: $x=737$, range $[1,1000]$, up to 10 queries.

Step 1: Query mid = 500
  Your program:  cout << "? 500" << endl;     // endl = newline + flush
  Judge responds: "higher"

  Search space: [501, 1000]    (500 candidates)
  Queries used: 1

Step 2: Query mid = 750
  Your program:  cout << "? 750" << endl;
  Judge responds: "lower"

  Search space: [501, 749]     (249 candidates)
  Queries used: 2

Step 3: Query mid = 625
  Your program:  cout << "? 625" << endl;
  Judge responds: "higher"

  Search space: [626, 749]     (124 candidates)
  Queries used: 3

Step 4: Query mid = 687
  Your program:  cout << "? 687" << endl;
  Judge responds: "higher"

  Search space: [688, 749]     (62 candidates)
  Queries used: 4

Step 5: Query mid = 718
  Your program:  cout << "? 718" << endl;
  Judge responds: "higher"

  Search space: [719, 749]     (31 candidates)
  Queries used: 5

  ... continues halving until found at query 10 ...

  Candidates remaining after each query:

  Query: 1    2    3    4    5    6    7    8    9   10
         |    |    |    |    |    |    |    |    |    |
  1000--500--249--124---62---31---15----7----3----1----*
         \    \    \    \    \    \    \    \    \
          each step halves the search space

After 10 queries: $1000/2^{10}=1000/1024<1$. Guaranteed to find $x$.

The Invariant

+--------------------------------------------------------------------+
| INVARIANT: After k queries, the candidate set has at most           |
| ceil(N / 2^k) elements. Always flush after printing a query.       |
| Always read the judge's response before issuing the next query.    |
+--------------------------------------------------------------------+

Why is this maintained? At each step, we query the midpoint, which splits the remaining interval into two halves. The judge's response tells us which half to keep, discarding at least half the candidates every time.

Look at Step 3 above: the space was $[501,749]$ (249 elements). We queried 625, splitting into $[501,624]$ (124) and $[626,749]$ (124). The judge said "higher", so we kept the right half. Without the flush at Step 3, the judge would never respond and the invariant would stall—not break mathematically, but break operationally. The flush is part of the invariant.

What the Code Won't Teach You

The deepest question in every interactive problem is: how do I extract the maximum information per query? Binary search answers it by buying 1 bit per query—each midpoint halves the search space. When the problem allows richer queries (asking about multiple elements at once, for instance), there may be a better information-theoretic strategy. Think of queries as purchases: the minimum number you need equals the entropy of the answer space divided by bits per query.

  Information per query:
  +---------------------------------------+
  | Query type       | Bits gained | Why   |
  +------------------+-------------+-------+
  | Yes/No           |     1 bit   | halves|
  | 1 of 3 answers   |   ~1.58 bit | /3    |
  | Distance (int)   |   log2(N)   | exact |
  +------------------+-------------+-------+
  |                                        |
  | Total bits needed = ceil(log2(|answer  |
  |   space|))                             |
  | Total queries >= bits_needed /         |
  |   bits_per_query                       |
  +----------------------------------------+

Debugging interactive problems is harder than debugging normal ones. You can't print intermediate values to stdout—the judge reads them as queries. Use stderr instead: cerr << "debug: lo=" << lo << " hi=" << hi << "\n";. The judge ignores stderr entirely, so you can leave those lines in on submission without disrupting the protocol. This trap catches everyone at least once.

  WRONG debugging:                      RIGHT debugging:
  +---------------------------+         +---------------------------+
  | cout << "debug: " << lo;  |         | cerr << "debug: " << lo; |
  |         |                 |         |         |                 |
  |         v                 |         |         v                 |
  | Judge reads "debug: 1"   |         | Goes to stderr (ignored   |
  | as a QUERY --> WA/RE     |         |  by judge) --> safe        |
  +---------------------------+         +---------------------------+

Not every interactive problem is binary search. "Guess a graph," "find a Hamiltonian path," or "determine a permutation via comparison queries" require entirely different strategies. The first decision is recognizing which category you are in: scalar guessing (binary search), graph/tree navigation (centroid or heavy-path queries), or order reconstruction (merge-sort comparisons).

With those categories in mind, here is how to spot interactive problems and choose a strategy.

When to Reach for This

Trigger phrases in problem statements:

• "This is an interactive problem"
• "You may ask at most $q$ queries"
• "The judge will respond with..."
• "Print ? to ask a query, ! to give the final answer"
• "Use flush after each query"

Counter-examples—looks interactive but is not:

• "Given an array, answer $q$ offline queries..."—this is standard offline queries, not interactive. You see all queries upfront.
• "Simulate a process with $q$ steps..."—sequential simulation, not judge-response interaction. See: 01-offline-queries.md.

---

Visual Intuition (Protocol Diagram)

The core communication protocol between your program and the judge:

  +------------+                     +------------+
  |  Your Code |                     |   Judge    |
  +------+-----+                     +-----+------+
         |                                 |
         |  "? 500\n"  (+ flush)           |
         |-------------------------------->|
         |                                 |  compares 500 with hidden x
         |          "higher\n"             |
         |<--------------------------------|
         |                                 |
         |  "? 750\n"  (+ flush)           |
         |-------------------------------->|
         |                                 |  compares 750 with hidden x
         |          "lower\n"              |
         |<--------------------------------|
         |                                 |
         |        ... more queries ...     |
         |                                 |
         |  "! 737\n"  (+ flush)           |
         |-------------------------------->|
         |                                 |  ACCEPTED
         |                                 |

What happens without flushing:

  +------------+                     +------------+
  |  Your Code |                     |   Judge    |
  +------+-----+                     +-----+------+
         |                                 |
         |  "? 500"  (stuck in buffer)     |
         |             X  <-- never sent   |
         |                                 |
         |  (waiting for response...)      |  (waiting for query...)
         |                                 |
         |        ** DEADLOCK **           |
         |        Time Limit Exceeded      |
         |                                 |

---

C++ STL Reference

Function / Mechanism	Header	What it does	Notes
cout << endl	<iostream>	Outputs '\n' and flushes the stream	Preferred for interactive problems
cout.flush()	<iostream>	Flushes cout buffer without newline	Use after '\n' if not using endl
cout << '\n'; cout.flush();	<iostream>	Equivalent to cout << endl	Explicit two-step version
fflush(stdout)	<cstdio>	Flushes C-style stdout buffer	Use if mixing printf/scanf
printf("? %d\n", x); fflush(stdout);	<cstdio>	C-style query output + flush	Faster than cout in some judges
ios::sync_with_stdio(false)	<iostream>	Decouples C/C++ I/O streams	Risky in interactive—be careful
cin.tie(nullptr)	<iostream>	Unties cin from cout	Do NOT use in interactive problems

Critical warning: In normal competitive programming, you reflexively add ios::sync_with_stdio(false); cin.tie(nullptr); for speed. In interactive problems, the second line is lethal: cin.tie(nullptr) unties cin from cout, so cout is not automatically flushed before cin reads. Either skip both lines or manually flush before every read.

  I/O Tie Behavior:

  DEFAULT (cin tied to cout):
  +--------+       +--------+       +-------+
  | cout<< |------>| FLUSH  |------>| cin>> |
  | query  |  auto | buffer |  then | read  |
  +--------+       +--------+       +-------+
  Judge sees query before you read --> OK

  AFTER cin.tie(nullptr):
  +--------+       +--------+       +-------+
  | cout<< |       | buffer |       | cin>> |
  | query  |       | (FULL) |       | read  |
  +--------+       +--------+       +-------+
      |                                 |
      +--- query stuck in buffer -------+
      |         DEADLOCK                |
      v                                 v

---

Implementation (Contest-Ready)

Minimal Contest Template

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

int main() {
    int lo = 1, hi = 1000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        cout << "? " << mid << endl;
        string resp;
        cin >> resp;
        if (resp == "higher") lo = mid + 1;
        else hi = mid;
    }
    cout << "! " << lo << endl;
    return 0;
}

Explained Version

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

int main() {
    // Do NOT add cin.tie(nullptr) -- it breaks interactive flushing.
    // Do NOT add ios::sync_with_stdio(false) unless you manually flush.

    int lo = 1, hi = 1000;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        // Print the query. '?' is the conventional query prefix.
        // endl = '\n' + flush. Both are essential.
        cout << "? " << mid << endl;

        // Read the judge's response. This blocks until the judge replies.
        // If we forgot to flush above, this blocks forever (deadlock).
        string resp;
        cin >> resp;

        // Narrow the search space based on the judge's answer.
        if (resp == "higher") {
            lo = mid + 1;   // hidden number is above mid
        } else {
            hi = mid;        // hidden number is mid or below
        }
    }

    // '!' is the conventional answer prefix. Flush after this too.
    cout << "! " << lo << endl;

    return 0;
}

---

Operations Reference

The table below summarizes query costs for the most common interactive patterns—use it to verify your strategy fits the query budget.

Operation	Query Cost	Total Queries	Notes
Binary search on $[1,N]$	1 per step	$\lceil {\log }_{2}N\rceil$	Most common pattern
Ternary search on $[1,N]$	2 per step	$2\lceil {\log }_{3/2}N\rceil$	For unimodal functions
Find element in graph ($n$ nodes)	1 per step	$O(\log n)$ with BFS-tree binary search	Advanced
Determine permutation ($n$ elements)	1 per pair	$O(n\log n)$ via merge sort queries	Comparison-based
Find edge in tree ($n$ nodes)	1 per step	$O(\log n)$ via centroid-path queries	Walk toward heavy child

Query Budget Analysis

How many queries does binary search need for typical competitive-programming ranges? The table below gives $\lceil {\log }_{2}N\rceil$ and the slack usually offered by problem setters.

  +------------------+-------------------------+----------------+
  | Search space N   | Queries needed (binary) | Common budget  |
  +------------------+-------------------------+----------------+
  | 10^3             |          10             |       10       |
  | 10^6             |          20             |     20-25      |
  | 10^9             |          30             |     30-35      |
  | 10^18            |          60             |     60-65      |
  +------------------+-------------------------+----------------+

Why do setters give extra queries? Three reasons:

1. Off-by-one protection. A budget of exactly $\lceil {\log }_{2}N\rceil$ demands a flawless loop. Giving 1–2 extra queries lets while (lo <= hi) style templates pass even though they may use one extra iteration compared to while (lo < hi).

2. Ternary search or 3-way responses. When the judge returns one of three answers (lower / higher / equal), each query yields only $\approx 1.58$ bits. For $N={10}^9$ you need $\lceil {\log }_2({10}^9)/{\log }_{2}3\rceil =19$ ternary steps, well inside a budget of 30. The extra margin covers strategies that don't extract the full 1.58 bits every time.

3. Non-uniform cost. Some problems give a richer query type (e.g., "ask the distance to a node") that can yield more than 1 bit. The budget accounts for the expected strategy, not the information-theoretic minimum.

Rule of thumb: if the budget is $\lceil {\log }_{2}N\rceil +5$ or more, the intended solution is probably not plain binary search—look for a richer query that gains more information. See Divide and Conquer for strategies that reduce by more than half per step.

---

Problem Patterns & Tricks

Binary Search Guessing Game

You have a hidden value in $[1,N]$ and $\lceil {\log }_{2}N\rceil$ queries. Binary search directly.

Trick: Watch for off-by-one. Some judges reply with respect to $\ge$ vs $>$. Read the problem statement carefully to decide hi = mid vs hi = mid - 1.

CF 1167B (Guess the Number), CF 679A (Bear and Reverse Rounding)

Binary Search on a Graph/Tree

Hidden node in a tree. Each query "is $x$ closer to $a$ or $b$?" or "what is the distance from $x$ to node $v$?" Use queries to narrow down the subtree.

Trick: Root the tree, then binary search on the path from root to the answer. Or use centroid decomposition to halve the candidate set each query.

// Pseudocode: binary search on tree path
while (candidates > 1) {
    pick node v that splits candidates roughly in half;
    cout << "? " << v << endl;
    int dist; cin >> dist;
    // prune candidates based on distance
}

CF 1370F (The Hidden Pair), CF 1364D (Ehab's Last Corollary)

Sorting via Comparisons

Hidden permutation. Each query asks "is $a[i]<a[j]$?" (the judge compares two elements). Reconstruct the sorted order.

Trick: Merge sort uses $O(n\log n)$ comparisons. This is optimal. Implement merge sort where each comparison is a query to the judge.

CF 1503D (Flip the Cards), CF 1556E (Equilibrium)

Adaptive Adversary Defense

The judge is adaptive—it doesn't fix the answer in advance but chooses responses to maximize your queries while staying consistent.

Trick: Always use a strategy that works against the worst case. Binary search is already worst-case optimal for guessing games. For more complex problems, think minimax: what query minimizes the maximum remaining candidates regardless of the response?

CF 843B (Interactive LowerBound), CF 1114D (Flood Fill)

Multi-Test Interactive

Multiple test cases in one run. After each test case, the judge sends a signal (often 1 for correct, -1 for wrong). If you get -1, you must exit immediately.

int t;
cin >> t;
while (t--) {
    // solve one test case interactively
    int result;
    cin >> result;
    if (result == -1) return 0;  // wrong answer -- exit immediately
}

Trick: Forgetting to handle -1 leads to Wrong Answer on all subsequent test cases, often surfacing as Idleness Limit Exceeded.

  Multi-test flow:

  +-------+     +-------+     +-------+     +------+
  | Test 1|---->| Test 2|---->| Test 3|---->| Done |
  | solve |     | solve |     | solve |     |      |
  +---+---+     +---+---+     +---+---+     +------+
      |             |             |
      v             v             v
  result: 1     result: 1     result: -1
  (correct)     (correct)     (WRONG!)
                                  |
                                  v
                          EXIT IMMEDIATELY!
                          (return 0)
                          
  If you DON'T exit on -1:
  +-------+     +-------+     +-------+     +-------+
  | Test 3|     | Test 4|     | Test 5|     |       |
  | WRONG |---->| reads |---->| reads |---->| ILE   |
  |       |     | garbage|    | garbage|    |       |
  +-------+     +-------+     +-------+     +-------+

CF 1697D (Guess The String), CF 1075B (Taxi drivers and Lyft)

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|  INTERACTIVE PROBLEMS -- QUICK REFERENCE                         |
+------------------------------------------------------------------+
|                                                                  |
|  FLUSHING (pick one):                                            |
|    cout << "? " << x << endl;       // C++ (recommended)        |
|    cout << "? " << x << '\n'; cout.flush();                     |
|    printf("? %d\n", x); fflush(stdout);   // C-style            |
|                                                                  |
|  DO NOT USE:                                                     |
|    cin.tie(nullptr);   // causes deadlock in interactive         |
|                                                                  |
|  QUERY FORMAT:                                                   |
|    "? <value>"   -- ask a query                                  |
|    "! <answer>"  -- submit final answer                          |
|                                                                  |
|  BINARY SEARCH TEMPLATE:                                         |
|    lo=1, hi=N; while(lo<hi) { mid=(lo+hi)/2;                    |
|    query mid; if(judge says higher) lo=mid+1; else hi=mid; }     |
|    answer lo;                                                    |
|                                                                  |
|  QUERY BUDGET:                                                   |
|    log2(10^9) = 30,  log2(10^6) = 20,  log2(10^3) = 10          |
|                                                                  |
|  MULTI-TEST: read result after each case; exit on -1             |
|                                                                  |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Forgetting to Flush

Symptom: Time Limit Exceeded or Idleness Limit Exceeded. Fix: Use endl instead of '\n'. Or add cout.flush() after every query.

Using cin.tie(nullptr)

Symptom: Deadlock. Your program waits for input; judge waits for output. Fix: Remove cin.tie(nullptr) from your interactive template entirely.

Off-by-One in Binary Search Bounds

Symptom: Wrong Answer on edge cases ($x=1$ or $x=N$). Fix: Trace through your loop with $x=1$ and $x=N$ by hand. The judge's comparison semantics—not your intuition—determine whether hi = mid or hi = mid - 1 is correct.

Worked example—tricky edge case: $x=1$, range $[1,8]$, budget = 3 queries.

  Using hi = mid (CORRECT for "lower means x <= mid"):

  lo=1, hi=8  -->  mid=4  -->  judge: "lower"  -->  hi=4
  lo=1, hi=4  -->  mid=2  -->  judge: "lower"  -->  hi=2
  lo=1, hi=2  -->  mid=1  -->  judge: "correct" -->  FOUND!
  Queries used: 3   Budget: 3   OK!

  Using hi = mid - 1 (WRONG for this judge protocol):

  lo=1, hi=8  -->  mid=4  -->  judge: "lower"  -->  hi=3
  lo=1, hi=3  -->  mid=2  -->  judge: "lower"  -->  hi=1
  lo=1, hi=1  -->  lo==hi, exit loop  -->  answer: 1
  Queries used: 2   But what if judge says "lower" means x < mid?
  Then x could be 1 OR 2 -- ambiguous!

  +-----------------------------------------------+
  | LESSON: The judge's semantics determine your  |
  | update rule. Read the problem TWICE.           |
  |                                                |
  | "lower" = x < mid   --> hi = mid - 1          |
  | "lower" = x <= mid  --> hi = mid               |
  +-----------------------------------------------+

Not Exiting on -1 in Multi-Test

Symptom: Wrong Answer or Runtime Error after a wrong guess. Fix: After reading the judge's verdict, check for -1 and return 0.

Mixing printf and cout

Symptom: Output appears out of order; judge misinterprets queries. Fix: Pick one I/O system and stick with it. If using both, ensure ios::sync_with_stdio(true) (the default) is in effect.

Debugging Locally: Two-Process Setup

You cannot test an interactive solution by running it in isolation—it needs a judge to talk to. Use a shell pipe or a Python interactor:

# Method 1: Named pipes (Linux/Mac)
mkfifo pipe1 pipe2
./judge < pipe1 > pipe2 &
./solution < pipe2 > pipe1

# Method 2: Python interactor
python3 interactor.py ./solution

Adaptive Judges

Some judges don't fix the hidden answer at the start. They choose responses consistent with all previous answers to make your life harder. Your strategy must work against worst-case responses, not just random ones. Binary search is already worst-case optimal for simple guessing—but for more complex problems, think carefully about what the adversary can do.

Mental Traps

Trap 1: "The same binary search template works as-is."

Your array binary search template probably uses while (lo <= hi), which can consume one more query than the budget allows. Verify the exact query count before submitting—a "find last true" template with a rounding-up midpoint can silently exceed the budget.

  WRONG thinking:                       RIGHT thinking:
  +---------------------------+         +---------------------------+
  | "My binary search works   |         | "How many queries does my |
  |  for arrays, it'll work   |         |  template use? Does it    |
  |  for interactive too."    |         |  match the budget?"       |
  +---------------------------+         +---------------------------+
                                        
  Template A: while(lo < hi)            Template B: while(lo <= hi)
    mid = lo + (hi-lo)/2                  mid = lo + (hi-lo)/2
    queries: ceil(log2(n))                queries: ceil(log2(n)) + 1
                  |                                    |
                  v                                    v
            Budget: 10?                          Budget: 10?
            n=1000 --> 10 OK                     n=1000 --> 11 WRONG!

Trap 2: "Flushing only at the end is fine."

The judge cannot respond until it receives your query—which means it must be flushed. Every query needs a flush immediately after it is printed, not just the final answer.

  WRONG: Flush at the end               RIGHT: Flush after each query
  +--------+         +-------+           +--------+         +-------+
  | Code   |         | Judge |           | Code   |         | Judge |
  +---+----+         +---+---+           +---+----+         +---+---+
      |                   |                  |                   |
      | query 1 (buffered)|                  | query 1 + FLUSH  |
      |       X           |                  |------------------>|
      | query 2 (buffered)|                  |    response 1     |
      |       X           |                  |<------------------|
      | (waiting...)      |                  | query 2 + FLUSH   |
      |   DEADLOCK        |                  |------------------>|
      |                   |                  |    response 2     |
      v                   v                  |<------------------|
                                             v                   v

Trap 3: "The problem guarantees the answer exists, so any strategy works."

Some interactive problems have an adaptive judge—the answer is chosen after seeing your queries, constrained only to stay consistent with previous responses. A strategy that works on average may fail against the adversary's worst case. Always design for worst-case.

  FIXED JUDGE:                          ADAPTIVE JUDGE:
  +---------------------------+         +---------------------------+
  | Hidden answer chosen      |         | No fixed answer! Judge    |
  | BEFORE your queries.      |         | picks responses to make   |
  | Any correct strategy      |         | your life HARDEST while   |
  | that finds it works.      |         | staying consistent.       |
  +---------------------------+         +---------------------------+
        |                                       |
        v                                       v
  Binary search: always OK              Must be WORST-CASE optimal
                                        (binary search still works
                                         for simple guessing games)

Common Judge Interaction Bugs

Each of the following bugs has cost someone a 30-minute contest penalty. They are distinct enough from the gotchas above to warrant their own list.

Bug 1—Forgetting to flush. Already discussed, but worth repeating: this is the #1 cause of Idleness Limit Exceeded. Always use endl or explicit flush().

Bug 2—Reading past end of input on -1. When the judge sends -1 (wrong answer signal), some contestants try to continue reading the next test case, consuming data that doesn't exist. This leads to Runtime Error or Idleness Limit Exceeded.

// WRONG: keeps running after -1
int verdict; cin >> verdict;
// should exit, but falls through to next iteration

// RIGHT: exit immediately
int verdict; cin >> verdict;
if (verdict == -1) return 0;

Bug 3—Printing debug output to stdout.cout << "debug: lo=" << lo; is read by the judge as a query. Use cerr for all debug output—the judge ignores stderr entirely.

Bug 4—Wrong query format (missing ? prefix). If the protocol requires ? 42 and you print just 42, the judge either misparses or rejects the query. Always include the prefix character.

// WRONG:
cout << mid << endl;

// RIGHT:
cout << "? " << mid << endl;

Bug 5—Submitting the answer with ? instead of !. A surprisingly common typo. The judge interprets your final answer as yet another query, either wasting your budget or returning a confusing response.

// WRONG:
cout << "? " << answer << endl;   // judge thinks this is a query!

// RIGHT:
cout << "! " << answer << endl;   // judge accepts the final answer

---

Self-Test

• [ ] Write a binary search interactive solution template that: (1) flushes after every query, (2) uses exactly ⌈log2(n)⌉ queries, (3) prints the answer with "!" prefix.
• [ ] Explain why not flushing causes TLE (deadlock) rather than WA.
• [ ] Compute the number of queries needed to binary search in [1, 10^9] and verify it's within a budget of 30.
• [ ] State how to print debug information in an interactive problem without corrupting the judge communication.
• [ ] Describe what "adaptive judge" means and how it changes your strategy.
• [ ] Write the two-process local testing setup (named pipes or Python interactor) from memory.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Guess the Number	CF 1167B	Easy	Basic binary search guessing game
2	Guess the Number	CF 679A	Easy	Binary search with rounding
3	Interactive Lower Bound	CF 843B	Easy-Med	Binary search in a linked list
4	XOR Guessing	CF 1207E	Medium	Two queries using bit partitioning
5	Lost Numbers	CF 1167C	Medium	4 queries to find a permutation of 6 numbers
6	Guess the Permutation	CF 1589D	Medium	Deduce a permutation interactively
7	The Hidden Pair	CF 1370F	Medium-Hard	Binary search on a tree path
8	Secret Sequence	CF 1292E	Hard	Reconstruct sequence with limited queries

---

Deeper Insights & Tactics

Interactive problems are decision trees at heart. Each query buys bits of information: a yes/no response gives 1 bit, a three-way lower/equal/higher gives ${\log }_{2}3\approx 1.58$ bits, and "what is the distance?" can give ${\log }_{2}N$ bits in one shot. The minimum number of queries is always $\lceil \text{entropy of answer space}/\text{bits per query}\rceil$. Once you internalize this, the query budget in the problem statement tells you the intended strategy immediately—"30 queries, $N={10}^9$" screams binary search; "2 queries" screams a bit-partition trick.

It is the 20 Questions game. You ask, they answer, you narrow down. The only twist is that if you mumble—forget to flush—the other player never hears you and the game freezes forever. Burn this mnemonic into your debugging checklist: "FLUSH or BUST".

Match the problem constraints to the likely technique:

  +------------------------------+-------------------------------+
  | Constraint clue              | Technique                     |
  +------------------------------+-------------------------------+
  | "at most 30 queries, N=10^9" | Binary search (1 bit/query)  |
  | "at most 2 queries"          | Bit-partition / XOR trick     |
  | "n log n queries, permutation"| Merge-sort comparisons       |
  | "queries on a tree"          | Centroid / heavy-path search  |
  | "adaptive judge"             | Worst-case / minimax strategy |
  | "budget >> log2(N)"          | Richer query, not plain BS    |
  +------------------------------+-------------------------------+

See Sorting and Searching for comparison-based lower bounds that apply directly to interactive sorting problems.

If I Had 5 Minutes

1. Flush after every output line—use endl, not '\n'.
2. Remove cin.tie(nullptr) from your template.
3. Binary search: while (lo < hi) uses exactly $\lceil {\log }_{2}N\rceil$ queries.
4. Use "? " for queries, "! " for the final answer.
5. Handle -1 from judge: if (verdict == -1) return 0;.

Rating Progression

  +---------------------------------------------------------------+
  | CF ~1200  |  Guess a number in [1,N] via binary search.       |
  |           |  Know how to flush. Handle one test case.          |
  +-----------+----------------------------------------------------+
  | CF ~1500  |  Multi-test interactive. Handle -1 exit.           |
  |           |  Bit-partition tricks (XOR Guessing).              |
  +-----------+----------------------------------------------------+
  | CF ~1800  |  Interactive on graphs/trees. Centroid-based       |
  |           |  search. Merge-sort query reconstruction.          |
  +-----------+----------------------------------------------------+
  | CF ~2100  |  Adaptive adversary. Information-theoretic lower   |
  |           |  bounds. Custom query design for max bits/query.   |
  +---------------------------------------------------------------+

Before You Code Checklist

  +------------------------------------------------------------------+
  |  BEFORE YOU CODE -- Interactive Problem Checklist                 |
  +------------------------------------------------------------------+
  |  [ ] 1. Read the query format TWICE ("?" vs "!" prefix)          |
  |  [ ] 2. Confirm flush method (endl / cout.flush / fflush)        |
  |  [ ] 3. Verify query budget vs ceil(log2(N))                     |
  |  [ ] 4. Check: is the judge adaptive or fixed?                   |
  |  [ ] 5. FLUSH! (yes, check this again -- it is that important)   |
  +------------------------------------------------------------------+

What Would You Do If...?

Scenario 1: You get Idleness Limit Exceeded but your logic looks correct.—Almost certainly a flush bug. Grep your code for every cout line and verify each one ends with endl or is followed by flush(). Also check that you didn't sneak in cin.tie(nullptr).

Scenario 2: The judge returns -1 on the very first test case but your local interactor works fine.—Your query format is wrong. Check: does the judge expect ? 42 or just 42? Is there a newline after the ! answer? Some judges require reading $n$ or $t$ before the first query.

Scenario 3: Your solution works for small $N$ but exceeds the query budget for large $N$.—You are using a while (lo <= hi) loop that does one extra iteration. Switch to while (lo < hi) with hi = mid (not mid - 1) to save that query.

Historical Note

Interactive problems on Codeforces emerged around 2016–2017, drawing on classical information-theoretic games—Ulam's Liar Game (1976) and Rényi's search with lies. The "20 Questions" game itself is centuries older, but the competitive-programming version adds the adversarial twist: the judge can be adaptive, playing to maximize your query count within the rules.

The Mistake That Teaches

Contest log, Codeforces Round #XXX, problem D:

I code the binary search in 4 minutes. Submit. Idleness Limit Exceeded. I stare at the code. The logic is textbook-perfect. I add endl—wait, I already have endl. I re-read. Then I see it: line 2 of main() says ios::sync_with_stdio(false); cin.tie(nullptr);. My muscle-memory contest template. The cin.tie(nullptr) untied cin from cout, so cout was not flushed before cin >> blocked. The judge and my program were both waiting for each other. Deadlock. I delete the line, resubmit, AC in 0.03s. Seven minutes wasted. The lesson burned in permanently: interactive problems get their own template. No cin.tie(nullptr). Ever.

When NOT to Use This

Interactive techniques are the wrong tool when:

• All queries are known upfront. If the problem hands you a batch of queries to answer offline, you see everything before writing a single line of output. See Sorting and Searching.
• You can precompute the answer. If the answer depends only on the given input and no hidden state is revealed incrementally, standard algorithms apply.
• The "interaction" is just multi-step simulation. Some problems describe a process in rounds but don't involve a judge at all. That's plain simulation (see Simulation).

Debug This

Find the bug in each snippet. Answers below.

Snippet 1—The Silent Query:

int main() {
    int lo = 1, hi = 1000000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        cout << "? " << mid << '\n';  // <-- BUG
        int resp; cin >> resp;
        if (resp == 1) lo = mid + 1;
        else hi = mid;
    }
    cout << "! " << lo << '\n';       // <-- BUG
}

Snippet 2—The Broken Tie:

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);                  // <-- BUG
    int lo = 1, hi = 1000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        cout << "? " << mid << endl;
        string s; cin >> s;
        if (s == "higher") lo = mid + 1;
        else hi = mid;
    }
    cout << "! " << lo << endl;
}

Snippet 3—The Wrong Prefix:

int main() {
    int lo = 1, hi = 1000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        cout << mid << endl;           // <-- BUG: missing "? "
        string s; cin >> s;
        if (s == "higher") lo = mid + 1;
        else hi = mid;
    }
    cout << "? " << lo << endl;        // <-- BUG: should be "!"
}

Snippet 4—The Zombie Process:

int main() {
    int t; cin >> t;
    while (t--) {
        int lo = 1, hi = 1000;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            cout << "? " << mid << endl;
            int r; cin >> r;
            if (r == -1) break;        // <-- BUG: break, not return
            if (r == 1) lo = mid + 1;
            else hi = mid;
        }
        cout << "! " << lo << endl;
    }
}

Answers

1. Missing flush. '\n' does not flush; use endl or add cout.flush().
2. cin.tie(nullptr) causes deadlock. Remove it—cout must auto-flush before cin reads in interactive problems.
3. Two prefix bugs. Queries need "? " prefix; the final answer needs "! " prefix, not "? ".
4. break instead of return 0 on -1. After the judge signals wrong answer, the next iteration reads garbage. Must return 0 immediately.

---

Further Reading

• Codeforces—Interactive Problems Guide—the original CF blog post on interactive problem conventions.
• cp-algorithms: Interactive Problems—general reference (check for interactive-specific content).
• CF Blog—How to Test Interactive Problems Locally—setting up local testing with interactors.
• See also: Binary Search for the foundational search technique.