SyntaxPilot
Courses/Competitive Programming/Lesson 84
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 84 of 90

Interactive problems

queued

These are the notes for Competitive Programming episode 84. Until now the judge gave your program all of its input at once and read the answer at the end. In an interactive problem the judge talks back: you print a question, it prints a reply, and your next question depends on that reply. Guess the Price hides x in [1, 10^9] and allows 30 questions: guessing 1, 2, 3, ... is Wrong Answer at question 31, halving the range uses exactly 30. To test at home we write a local judge in the same file. Then the bug that only interactive problems have: a question left in the output buffer never reaches the judge, the two programs wait for each other, and the verdict is Idleness Limit Exceeded; our fast-I/O template line cin.tie(nullptr) makes this easy to hit. Find the Peak hides an array and allows 40 questions: reading everything fails, walking uphill and halving uses at most 34. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real. The interactor runs (two programs connected by pipes) were done with the Python harness from the Mini project.

The real-life hook

A shopkeeper hides the price of something and says: guess it. You can't see the tag. You ask "is it 500 or more?", he says yes or no, and your next question depends on his answer. He only has patience for so many questions: ask too many and you lose. That is an interactive problem: a hidden value (the judge holds it), questions and replies (one at a time), and a query limit.

The second picture is a letter left in your bag. You write a letter but, to save trips, you keep it in your bag and post several together later. cout does the same: it collects text in a buffer and writes it out in big chunks. The letter is only on its way when it goes into the post box: for cout that is a flush. If you sit and wait for a reply to a letter that is still in your bag, nobody moves: the judge waits for your question, you wait for its answer.

How an interactive problem works

  • Your program and the judge's program (the interactor) run at the same time.
  • They are connected by two pipes: what you print to stdout goes into the interactor's input; what the interactor prints comes into your stdin.
  • The problem statement fixes the protocol: the exact format of a question (? y), of a reply (< or >=), and of the final answer (! x), plus how many questions you may ask.
  • There is no fixed input file: the replies depend on your questions. That is why you write a local judge to test at home.
  • After every line you print you must flush, so that the line really leaves your program now.

Problem I1 · Guess the Price

(Written for this course.)

  • The judge hides an integer x, 1 ≤ x ≤ 10^9.
  • You print ? y. The judge replies < if x < y, and >= otherwise.
  • At most 30 questions. Then print ! x (the answer does not count as a question).
  • After every line you print: flush the output.
  • If you ask a 31st question (or a malformed one), the judge replies -1 and stops: exit at once.

Example dialogue (the real start of the run against the interactor below, hidden x = 500000000):

program: ? 500000001
judge:   <
program: ? 250000001
judge:   >=
program: ? 375000001
judge:   >=
...
program: ! 500000000

A judge of your own (one by one: Wrong Answer)

The local judge is a struct in the same file: it holds the hidden x, counts the questions, answers ask, stops with Wrong Answer at question 31, and answer checks the guess. The hidden price is read from the input box. The obvious strategy asks "is it 2 or more? 3 or more? ..." and stops at the first <.

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

struct Judge {                                      // plays the judge on your own computer
    ll x;                                           // the hidden price
    int used = 0;
    string ask(ll y) {                              // "? y"
        if (++used > 30) { cout << "Wrong Answer: more than 30 questions\n"; exit(0); }
        return x < y ? "<" : ">=";
    }
    void answer(ll y) {                             // "! y"
        cout << (y == x ? "Accepted" : "Wrong Answer") << " in " << used << " questions\n";
    }
};

int main() {
    Judge J;
    cin >> J.x;                                     // local test: the hidden price
    for (ll y = 2; ; y++)                           // is it 1? is it 2? ...
        if (J.ask(y) == "<") { J.answer(y - 1); break; }
}

Input 7:

Accepted in 7 questions

Input 500000000:

Wrong Answer: more than 30 questions

One by one needs up to 10^9 questions.

Every question should halve the range

Keep the range [lo, hi] where x can still be; at first [1, 10^9]. Ask about the middle:

  • mid = (lo + hi + 1) / 2. If the reply is >=, x ≥ mid: keep [mid, hi]. If <: keep [lo, mid − 1].
  • Why the + 1? The >= branch sets lo = mid. With lo = 4, hi = 5, (lo + hi) / 2 = 4, a >= reply keeps [4, 5] and the loop never ends. Rounding up makes mid > lo, so both branches shrink the range. Changing only that line of the program below to (lo + hi) / 2 really gives Wrong Answer: more than 30 questions for x = 500000000 and for x = 1 (the local judge stops the endless loop), and Accepted in 29 questions for x = 7: a bug that hides on some inputs. (The rule: if a branch keeps mid on the low side, lo = mid, round up; if it keeps it on the high side, hi = mid, round down, as in Problem I2.)
  • Each reply throws away half: 10^9 → 5·10^8 → ... → 1. 2^30 = 1073741824 ≥ 10^9, so 30 questions are always enough.
  • The query limit is a hint: 30 ≈ log2(10^9) means binary search. 40 for 10^5 means about two questions per halving (Problem I2).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Judge {                                      // plays the judge on your own computer
    ll x;                                           // the hidden price
    int used = 0;
    string ask(ll y) {                              // "? y"
        if (++used > 30) { cout << "Wrong Answer: more than 30 questions\n"; exit(0); }
        return x < y ? "<" : ">=";
    }
    void answer(ll y) {                             // "! y"
        cout << (y == x ? "Accepted" : "Wrong Answer") << " in " << used << " questions\n";
    }
};

ll solve(Judge& J) {
    ll lo = 1, hi = 1000000000;                     // x is somewhere in [lo, hi]
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        if (J.ask(mid) == ">=") lo = mid;           // x >= mid
        else hi = mid - 1;                          // x < mid
    }
    return lo;
}

int main() {
    Judge J;
    cin >> J.x;
    J.answer(solve(J));
}

Input 500000000:

Accepted in 30 questions

Input 1:

Accepted in 29 questions

Input 1000000000:

Accepted in 30 questions

x = 1 needs only 29: with mid rounded up, the lower part [lo, mid − 1] is sometimes one shorter than the upper part, so going left all the time reaches size 1 one step early.

Stress test against the local judge

A thousand random prices plus the four edges, each against a fresh judge, recording the most questions ever used:

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

struct Judge {                                      // plays the judge on your own computer
    ll x;                                           // the hidden price
    int used = 0;
    string ask(ll y) {                              // "? y"
        if (++used > 30) { cout << "Wrong Answer: more than 30 questions\n"; exit(0); }
        return x < y ? "<" : ">=";
    }
    void answer(ll y) {                             // "! y"
        cout << (y == x ? "Accepted" : "Wrong Answer") << " in " << used << " questions\n";
    }
};

ll solve(Judge& J) {
    ll lo = 1, hi = 1000000000;                     // x is somewhere in [lo, hi]
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        if (J.ask(mid) == ">=") lo = mid;           // x >= mid
        else hi = mid - 1;                          // x < mid
    }
    return lo;
}

int main() {
    mt19937 gen(84);
    vector<ll> tests = {1, 2, 999999999, 1000000000};   // the edges first
    for (int i = 0; i < 1000; i++) tests.push_back(gen() % 1000000000 + 1);
    int most = 0;
    for (ll x : tests) {
        Judge J;
        J.x = x;
        if (solve(J) != x) { cout << "wrong for x = " << x; return 0; }
        most = max(most, J.used);
    }
    cout << "all " << tests.size() << " hidden prices found, at most " << most << " questions";
}
all 1004 hidden prices found, at most 30 questions

A local judge means free tests: no input files to write, and the question count is checked too.

What you actually submit

On the real judge there is no struct: asking is printing, and the reply is read from standard input. Your output goes into the interactor's input and its output comes into yours: two programs talking through a pipe.

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

int main() {                       // what you submit
    long long lo = 1, hi = 1000000000;
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        cout << "? " << mid << endl;   // endl = "\n" + flush
        string r;
        cin >> r;                       // the judge replies
        if (r == ">=") lo = mid;
        else hi = mid - 1;
    }
    cout << "! " << lo << endl;
}

Every line ends with endl, not "\n": endl writes the newline and flushes.

REAL1 talking to a real interactor

The Mini project's harness starts REAL1 as a child process, connects it with two pipes, plays the judge with hidden x = 500000000, and records the dialogue (first and last lines; 61 lines in total: 30 questions, 30 replies, 1 answer):

$ python3 interactor.py i1 500000000 -- ./REAL1
program: ? 500000001
judge:   <
program: ? 250000001
judge:   >=
program: ? 375000001
judge:   >=
... (49 more lines) ...
judge:   >=
program: ? 499999999
judge:   >=
program: ? 500000000
judge:   >=
program: ! 500000000
verdict: Accepted in 30 questions

The same 30 questions as the local judge's Accepted in 30 questions: the local judge and the real protocol agree.

The unsent letter: flushing

cout does not write every character at once; it collects text in the output buffer and writes it out when the buffer is full, when the program ends normally, or when you flush. When your output goes to a pipe (always, on a judge), a "\n" alone does not flush.

This program prints a question with "\n" and is then stopped before it ends, the way a judge kills a program that waits too long (abort() ends the program at once, without the normal clean-up that would flush the buffer):

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

int main() {
    cout << "? 500000000\n";         // sits in the output buffer
    // ... now we wait for the judge's reply, which never comes ...
    abort();                         // stop here, the way a judge kills a stuck program
}

The output is empty. The question was still in the buffer when the program died, so nobody ever saw it. On a judge that is Idleness Limit Exceeded. Now with endl:

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

int main() {
    cout << "? 500000000" << endl;   // written out at once
    // ... now we wait for the judge's reply, which never comes ...
    abort();                         // stop here, the way a judge kills a stuck program
}
? 500000000

The question is out, even though the program died right after. (The shell also reports Aborted on stderr for both programs; exit code 134.)

Why it "works on my machine". When stdout is a terminal, the C library flushes at every newline (line buffering). Run in a terminal (a pseudo-terminal via script), FLUSH_BAD really prints ? 500000000; piped into another program it prints nothing. A judge always uses pipes, so test through a pipe.

The cin.tie trap

Normally cin is tied to cout: before cin reads anything, it flushes cout for you. That is why many beginners never hit this bug. But our contest template (since episode 2) has:

ios::sync_with_stdio(false);
cin.tie(nullptr);

cin.tie(nullptr) removes exactly that automatic flush, to make output fast. Here is REAL1 with the template and "\n":

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

int main() {                       // the fast-I/O template, and "\n" instead of endl
    ios::sync_with_stdio(false);
    cin.tie(nullptr);              // cin no longer flushes cout before reading
    long long lo = 1, hi = 1000000000;
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        cout << "? " << mid << "\n";   // stays in the buffer
        string r;
        cin >> r;                       // waits for a reply to a question never sent
        if (r == ">=") lo = mid;
        else hi = mid - 1;
    }
    cout << "! " << lo << "\n";
}

Against the interactor (hidden x = 500000000, 3 s of silence allowed):

$ python3 interactor.py i1 500000000 -- ./REAL1_NOFLUSH
verdict: Idleness Limit Exceeded (no line for 3 s)

Not one line reached the judge: ? 500000001 stayed in the buffer, the program blocked in cin >> r, the interactor blocked waiting for a question, and after 3 s the harness killed it (real time 3.03 s). The same code without the two template lines (so cin is still tied to cout) and still with "\n":

$ python3 interactor.py i1 500000000 -- ./REAL1_TIED
verdict: Accepted in 30 questions

The tie flushed cout before every read. The safe habit is to flush yourself on every line anyway.

Flushing in every language

Language Flush after each line
C++ cout cout << ... << endl; or cout << "\n"; cout.flush(); (or << flush)
C printf printf("? %lld\n", y); fflush(stdout);
Java System.out.println(...); System.out.flush();
Python print(..., flush=True)

Python detail, checked through the pipes: input() flushes stdout before reading, so a Python solution without flush=True that reads with input() was still Accepted in 30 questions; the same program reading with sys.stdin.readline() got Idleness Limit Exceeded (no line for 3 s). (If the environment variable PYTHONUNBUFFERED=1 is set, Python never buffers and both pass, which hides the bug.) Write flush=True and don't depend on either.

Speed. Interactive problems print a few dozen lines, not millions: flushing every line costs nothing here.

The -1 reply convention

On many judges a bad question (too many, or out of range) gets the reply -1, and the judge stops listening. If you keep reading and printing, you get strange verdicts (the judge is gone; your reads fail). Exit at once. One by one, against the interactor, with an if (r == "-1") return 0; check:

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

int main() {                         // one by one, against the real protocol
    for (long long y = 2; ; y++) {
        cout << "? " << y << endl;
        string r;
        cin >> r;
        if (r == "-1") return 0;     // the judge has stopped: exit at once
        if (r == "<") { cout << "! " << y - 1 << endl; return 0; }
    }
}
$ python3 interactor.py i1 500000000 -- ./LIN_REAL
program: ? 2
judge:   >=
program: ? 3
judge:   >=
program: ? 4
judge:   >=
... (50 more lines) ...
program: ? 30
judge:   >=
program: ? 31
judge:   >=
program: ? 32
judge:   -1
verdict: Wrong Answer: question 31

With hidden x = 7 the same program gets verdict: Accepted in 7 questions, matching the local judge.

Adaptive judges

Some judges don't fix x at the start: an adaptive judge picks each reply to make your life hardest, keeping only "some x is still consistent with every reply". Your answer is accepted only if it is the only possible x left. Binary search doesn't care: every reply leaves at most half the range either way. The harness has an adaptive mode that always keeps the bigger part:

$ python3 interactor.py i1 adaptive -- ./REAL1
program: ? 500000001
judge:   >=
program: ? 750000001
judge:   >=
program: ? 875000001
judge:   >=
... (49 more lines) ...
judge:   >=
program: ? 999999999
judge:   >=
program: ? 1000000000
judge:   >=
program: ! 1000000000
verdict: Accepted in 30 questions

Lesson: never rely on a "lucky" fixed x (for example a random guess); count the questions in the worst case.

Problem I2 · Find the Peak

(Written for this course.)

  • A hidden array a[1..n], all values different, 1 ≤ n ≤ 10^5. The judge first prints n.
  • You print ? i (1 ≤ i ≤ n); the judge replies a[i].
  • Find any peak: an index i with a[i] bigger than both neighbours (outside the array the height is −∞, so the ends can be peaks). Print ! i.
  • At most 40 questions; a 41st gets -1. Flush after every line.

Think of the values as heights along a mountain trail. The local judges below read n and the array from the input instead (sample 7 / 3 8 5 1 4 6 2). Example dialogue, the real run of the I2 solution against the interactor on the sample:

judge:   7
program: ? 4
judge:   1
program: ? 5
judge:   4
program: ? 6
judge:   6
program: ? 7
judge:   2
program: ? 5
judge:   4
program: ? 6
judge:   6
program: ! 6
verdict: Accepted: index 6, 6 questions

Attempt 1: read the whole trail

The local judge holds the array, counts questions, and checks that the answer is a real peak. Ask every height, keep the highest:

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

struct Judge {
    vector<ll> a;                                   // a[1..n], all different
    int n, used = 0;
    ll ask(int i) {                                 // "? i"
        if (++used > 40) { cout << "Wrong Answer: more than 40 questions\n"; exit(0); }
        return a[i];
    }
    void answer(int i) {                            // "! i": is a[i] bigger than both neighbours?
        ll L = i > 1 ? a[i - 1] : LLONG_MIN, R = i < n ? a[i + 1] : LLONG_MIN;
        cout << (a[i] > L && a[i] > R ? "Accepted" : "Wrong Answer") << ": index " << i << ", " << used << " questions\n";
    }
};

int main() {
    Judge J;
    cin >> J.n;
    J.a.resize(J.n + 2);
    for (int i = 1; i <= J.n; i++) cin >> J.a[i];
    int best = 1;
    for (int i = 1; i <= J.n; i++)                  // read the whole array
        if (J.ask(i) > J.ask(best)) best = i;
    J.answer(best);
}

Input 7 / 3 8 5 1 4 6 2:

Accepted: index 2, 14 questions

Index 2, height 8, but 14 questions already (ask is called twice per step). A hundred thousand heights (mt19937 gen(84), a shuffle of 1..100000):

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

struct Judge {
    vector<ll> a;                                   // a[1..n], all different
    int n, used = 0;
    ll ask(int i) {                                 // "? i"
        if (++used > 40) { cout << "Wrong Answer: more than 40 questions\n"; exit(0); }
        return a[i];
    }
    void answer(int i) {                            // "! i": is a[i] bigger than both neighbours?
        ll L = i > 1 ? a[i - 1] : LLONG_MIN, R = i < n ? a[i + 1] : LLONG_MIN;
        cout << (a[i] > L && a[i] > R ? "Accepted" : "Wrong Answer") << ": index " << i << ", " << used << " questions\n";
    }
};

int main() {
    mt19937 gen(84);
    Judge J;
    J.n = 100000;                                   // 100000 different heights
    J.a.resize(J.n + 2);
    for (int i = 1; i <= J.n; i++) J.a[i] = i;
    shuffle(J.a.begin() + 1, J.a.begin() + J.n + 1, gen);
    int best = 1;
    for (int i = 1; i <= J.n; i++)                  // read the whole array
        if (J.ask(i) > J.ask(best)) best = i;
    J.answer(best);
}
Wrong Answer: more than 40 questions

Wrong Answer at question 41: we can't look at the whole trail.

Walk uphill, and throw away half

  • Stand at mid and look one step right: ask a[mid] and a[mid + 1].
  • a[mid] < a[mid + 1]: uphill to the right → a peak in [mid + 1, hi].
  • a[mid] > a[mid + 1]: downhill → a peak in [lo, mid] (mid itself may be it).
  • Why must there be one? Walk uphill from mid in that direction: you can't climb forever, the trail ends in −∞, so you stop at a peak, and it is inside the kept part. The invariant: [lo, hi] always contains a peak of the whole array (the borders of the kept part are lower than their outside neighbours, or are the array's ends).
  • Here the branch is hi = mid, so mid rounds down: mid = (lo + hi) / 2, and mid + 1 ≤ hi always exists.
  • Trace on 3 8 5 1 4 6 2: mid 4 (1 < 4) → [5, 7]; mid 6 (6 > 2) → [5, 6]; mid 5 (4 < 6) → [6, 6]. Index 6, height 6, a peak.
  • log2(10^5) ≈ 17 halvings × 2 questions = 34 ≤ 40.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Judge {
    vector<ll> a;                                   // a[1..n], all different
    int n, used = 0;
    ll ask(int i) {                                 // "? i"
        if (++used > 40) { cout << "Wrong Answer: more than 40 questions\n"; exit(0); }
        return a[i];
    }
    void answer(int i) {                            // "! i": is a[i] bigger than both neighbours?
        ll L = i > 1 ? a[i - 1] : LLONG_MIN, R = i < n ? a[i + 1] : LLONG_MIN;
        cout << (a[i] > L && a[i] > R ? "Accepted" : "Wrong Answer") << ": index " << i << ", " << used << " questions\n";
    }
};

int peak(Judge& J) {
    int lo = 1, hi = J.n;                           // a peak is in [lo, hi]
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (J.ask(mid) < J.ask(mid + 1)) lo = mid + 1;   // uphill to the right
        else hi = mid;                              // downhill: a peak at mid or left
    }
    return lo;
}

int main() {
    Judge J;
    cin >> J.n;
    J.a.resize(J.n + 2);
    for (int i = 1; i <= J.n; i++) cin >> J.a[i];
    J.answer(peak(J));
}

Input 7 / 3 8 5 1 4 6 2:

Accepted: index 6, 6 questions

A different peak from before, and that's fine: any peak is accepted. Edge case, a trail of one point (input 1 / 42):

Accepted: index 1, 0 questions

A single point is always a peak. A hundred thousand heights:

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

struct Judge {
    vector<ll> a;                                   // a[1..n], all different
    int n, used = 0;
    ll ask(int i) {                                 // "? i"
        if (++used > 40) { cout << "Wrong Answer: more than 40 questions\n"; exit(0); }
        return a[i];
    }
    void answer(int i) {                            // "! i": is a[i] bigger than both neighbours?
        ll L = i > 1 ? a[i - 1] : LLONG_MIN, R = i < n ? a[i + 1] : LLONG_MIN;
        cout << (a[i] > L && a[i] > R ? "Accepted" : "Wrong Answer") << ": index " << i << ", " << used << " questions\n";
    }
};

int peak(Judge& J) {
    int lo = 1, hi = J.n;                           // a peak is in [lo, hi]
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (J.ask(mid) < J.ask(mid + 1)) lo = mid + 1;   // uphill to the right
        else hi = mid;                              // downhill: a peak at mid or left
    }
    return lo;
}

int main() {
    mt19937 gen(84);
    Judge J;
    J.n = 100000;                                   // 100000 different heights
    J.a.resize(J.n + 2);
    for (int i = 1; i <= J.n; i++) J.a[i] = i;
    shuffle(J.a.begin() + 1, J.a.begin() + J.n + 1, gen);
    J.answer(peak(J));
}
Accepted: index 14450, 34 questions

Stress test

300 random trails, lengths 1, 2 and 3 first, then random lengths up to 10^5. assign(J.n + 2, LLONG_MIN) puts −∞ at positions 0 and n + 1, so the check a[i] > a[i − 1] && a[i] > a[i + 1] works at the ends too:

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

struct Judge {
    vector<ll> a;                                   // a[1..n], all different
    int n, used = 0;
    ll ask(int i) {                                 // "? i"
        if (++used > 40) { cout << "Wrong Answer: more than 40 questions\n"; exit(0); }
        return a[i];
    }
    void answer(int i) {                            // "! i": is a[i] bigger than both neighbours?
        ll L = i > 1 ? a[i - 1] : LLONG_MIN, R = i < n ? a[i + 1] : LLONG_MIN;
        cout << (a[i] > L && a[i] > R ? "Accepted" : "Wrong Answer") << ": index " << i << ", " << used << " questions\n";
    }
};

int peak(Judge& J) {
    int lo = 1, hi = J.n;                           // a peak is in [lo, hi]
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (J.ask(mid) < J.ask(mid + 1)) lo = mid + 1;   // uphill to the right
        else hi = mid;                              // downhill: a peak at mid or left
    }
    return lo;
}

int main() {
    mt19937 gen(84);
    int most = 0;
    for (int it = 1; it <= 300; it++) {
        Judge J;
        J.n = it <= 3 ? it : gen() % 100000 + 1;   // n = 1, 2, 3 first
        J.a.assign(J.n + 2, LLONG_MIN);
        for (int i = 1; i <= J.n; i++) J.a[i] = i;
        shuffle(J.a.begin() + 1, J.a.begin() + J.n + 1, gen);
        int i = peak(J);
        if (!(J.a[i] > J.a[i - 1] && J.a[i] > J.a[i + 1])) { cout << "not a peak on test " << it; return 0; }
        most = max(most, J.used);
    }
    cout << "all 300 arrays: a real peak, at most " << most << " questions";
}
all 300 arrays: a real peak, at most 34 questions

The real I2 against the interactor

The submit-ready solution (in the last section) against the harness, n = 100000 (a shuffle by Python's random.Random(84), a different array from mt19937 gen(84), so a different peak):

$ python3 interactor.py i2 84 100000 -- ./i2
judge:   100000
program: ? 50000
judge:   11129
program: ? 50001
judge:   49343
program: ? 75000
... (54 more lines) ...
judge:   33586
program: ? 72895
judge:   24806
program: ? 72896
judge:   52828
program: ! 72896
verdict: Accepted: index 72896, 32 questions

Complexity vs the constraints

In interactive problems the scarce thing is questions, not seconds; the work between questions is tiny.

Method Questions (worst case) Limit Verdict
guess 1, 2, 3, ... up to 10^9 30 Wrong Answer at question 31
halve the price range ⌈log2 10^9⌉ = 30 30 Accepted (at most 30 in 1004 tests)
read the whole trail 2n = 2·10^5 40 Wrong Answer at question 41
walk uphill, halve 2·⌈log2 10^5⌉ = 34 40 Accepted (at most 34 in 300 tests)

Time: O(log) work per test; memory O(1) for I1 (the real solution stores nothing) and O(1) for I2 (the judge holds the array, not you).

Common mistakes (and the real outputs)

Mistake What you see Why Fix
"\n" and no flush, then abort() empty output (FLUSH_BAD) the question stays in the buffer endl / cout.flush()
cin.tie(nullptr) from the template + "\n" Idleness Limit Exceeded (no line for 3 s) no automatic flush before cin flush every line
Python sys.stdin.readline() without flush=True Idleness Limit Exceeded (no line for 3 s) stdout to a pipe is block-buffered print(..., flush=True)
asking one by one Wrong Answer: more than 30 questions the limit is log-sized halve the range
reading the whole array Wrong Answer: more than 40 questions 2n questions walk uphill
mid = (lo + hi) / 2 with lo = mid Wrong Answer: more than 30 questions (x = 500000000 and x = 1) stuck at hi = lo + 1: the range doesn't shrink (lo + hi + 1) / 2
reading after the judge says -1 random verdicts the judge has stopped exit at once on -1
testing only in a terminal "works on my machine" a terminal flushes at every newline test through a pipe

Mini project: a reusable interactor harness

A local judge inside your file is quick, but the real thing is two separate programs. This Python harness starts your program (any language), connects its stdin and stdout with two pipes, plays the judge, counts questions, replies -1 past the limit, stops a silent program after 3 s (Idleness Limit Exceeded) and prints the transcript (first and last 6 lines) and the verdict. It has three judges: I1 with a fixed x, I1 adaptive, and I2 on the sample or on a random permutation.

# interactor.py: a local judge that talks to your program through two pipes.
#   python3 interactor.py i1 X        -- ./solution     (Guess the Price, hidden x = X)
#   python3 interactor.py i1 adaptive -- ./solution     (x is never fixed: the judge keeps the bigger half)
#   python3 interactor.py i2 SEED N   -- ./solution     (Find the Peak, a random permutation of 1..N)
import subprocess, sys, threading, random

def run(cmd, judge, idle=3.0):
    p = subprocess.Popen(cmd, stdin=subprocess.PIPE, stdout=subprocess.PIPE, text=True, bufsize=1)
    log, timer = [], [None]
    state = {"idle": False}
    def kill():
        state["idle"] = True
        p.kill()
    def send(s):                                     # judge -> program, flushed at once
        log.append("judge:   " + s)
        try:
            p.stdin.write(s + "\n"); p.stdin.flush()
        except BrokenPipeError:
            pass
    def recv():                                      # program -> judge, at most `idle` seconds of silence
        timer[0] = threading.Timer(idle, kill); timer[0].start()
        line = p.stdout.readline()
        timer[0].cancel()
        if line == "":
            return None
        log.append("program: " + line.rstrip("\n"))
        return line.split()
    verdict = judge(send, recv)
    if state["idle"]:
        verdict = "Idleness Limit Exceeded (no line for %.0f s)" % idle
    try:
        p.stdin.close()
    except BrokenPipeError:
        pass
    p.wait()
    return log, verdict

def judge_i1(x, limit=30):
    lo, hi = 1, 10**9                                # for the adaptive judge: every x still possible
    def judge(send, recv):
        nonlocal lo, hi
        used = 0
        while True:
            t = recv()
            if t is None: return "Wrong Answer: the program stopped without an answer"
            if t[0] == "!":
                y = int(t[1])
                if x == "adaptive":
                    ok = lo == hi == y
                    return ("Accepted" if ok else "Wrong Answer (%d..%d still possible)" % (lo, hi)) + " in %d questions" % used
                return ("Accepted" if y == x else "Wrong Answer") + " in %d questions" % used
            used += 1
            y = int(t[1])
            if used > limit or not (1 <= y <= 10**9):
                send("-1"); return "Wrong Answer: question %d" % used
            if x == "adaptive":                      # answer so that the bigger part survives
                if hi - y + 1 >= y - lo: lo = max(lo, y); send(">=")
                else: hi = min(hi, y - 1); send("<")
            else:
                send("<" if x < y else ">=")
    return judge

def judge_i2(a, limit=40):
    n = len(a)
    def judge(send, recv):
        send(str(n))
        used = 0
        while True:
            t = recv()
            if t is None: return "Wrong Answer: the program stopped without an answer"
            i = int(t[1])
            if t[0] == "!":
                L = a[i - 2] if i > 1 else float("-inf")
                R = a[i] if i < n else float("-inf")
                ok = 1 <= i <= n and a[i - 1] > L and a[i - 1] > R
                return ("Accepted" if ok else "Wrong Answer") + ": index %d, %d questions" % (i, used)
            used += 1
            if used > limit or not (1 <= i <= n):
                send("-1"); return "Wrong Answer: question %d" % used
            send(str(a[i - 1]))
    return judge

if __name__ == "__main__":
    sep = sys.argv.index("--")
    args, cmd = sys.argv[1:sep], sys.argv[sep + 1:]
    if args[0] == "i1":
        j = judge_i1("adaptive" if args[1] == "adaptive" else int(args[1]))
    else:
        if args[1] == "sample":
            a = [3, 8, 5, 1, 4, 6, 2]
        else:
            rng = random.Random(int(args[1])); a = list(range(1, int(args[2]) + 1)); rng.shuffle(a)
        j = judge_i2(a)
    log, verdict = run(cmd, j)
    if len(log) <= 16:
        print("\n".join(log))
    else:
        print("\n".join(log[:6])); print("... (%d more lines) ..." % (len(log) - 12)); print("\n".join(log[-6:]))
    print("verdict: " + verdict)

Usage (all the transcripts in these notes come from it):

python3 interactor.py i1 500000000 -- ./REAL1
python3 interactor.py i1 adaptive  -- java -cp . Main
python3 interactor.py i2 sample    -- python3 i2.py
python3 interactor.py i2 84 100000 -- ./i2

Extensions: a judge that lies once (Practice 3), a judge for Practice 1's <, =, > replies, or a loop that runs your solution against 100 random hidden values and reports the worst question count.

Practice

These are the homework problems from the episode, written for this course. Each solution uses a local judge in the same file and a stress test; all outputs are real.

1. Replies <, = or >. The judge hides x in [1, 10^9]; ? y gets < if x < y, = if x = y, > if x > y. At most 30 questions; stop as soon as you get =.

Solution

Plain binary search with mid = (lo + hi) / 2: = ends it, < keeps [lo, mid − 1], > keeps [mid + 1, hi]. Each reply removes mid as well as half of the rest, so the range 10^9 needs at most ⌈log2(10^9 + 1)⌉ = 30 questions.

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

struct Judge {                                      // replies "<", "=" or ">"
    ll x;
    int used = 0;
    string ask(ll y) {                              // "? y"
        if (++used > 30) { cout << "Wrong Answer: more than 30 questions\n"; exit(0); }
        return x < y ? "<" : x == y ? "=" : ">";
    }
};

ll solve(Judge& J) {
    ll lo = 1, hi = 1000000000;                     // x is somewhere in [lo, hi]
    while (true) {
        ll mid = (lo + hi) / 2;
        string r = J.ask(mid);
        if (r == "=") return mid;                   // found: stop asking
        if (r == "<") hi = mid - 1;                 // x < mid
        else lo = mid + 1;                          // x > mid
    }
}

int main() {
    mt19937 gen(84);
    vector<ll> tests = {1, 2, 500000000, 999999999, 1000000000};
    for (int i = 0; i < 100000; i++) tests.push_back(gen() % 1000000000 + 1);
    int most = 0;
    for (ll x : tests) {
        Judge J;
        J.x = x;
        if (solve(J) != x) { cout << "wrong for x = " << x; return 0; }
        most = max(most, J.used);
    }
    cout << "all " << tests.size() << " found, at most " << most << " questions";
}
all 100005 found, at most 30 questions

2. Find a hidden permutation. The judge hides a permutation a[1..n] of 1..n, n ≤ 1000. ? i j asks "is a[i] < a[j]?". At most 9000 questions. Print the whole permutation.

Solution

Sort the positions 1..n by their hidden value, with the judge as the comparison. Merge sort uses at most n⌈log2 n⌉ − 2^⌈log2 n⌉ + 1 = 10000 − 1024 + 1 = 8977 comparisons for n = 1000, under 9000. The k-th smallest position holds the value k + 1 (0-based k). (Write your own merge sort: std::sort and std::stable_sort don't promise this bound.)

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

struct Judge {                                      // a hidden permutation a[1..n]
    vector<int> a;
    int n, used = 0, limit;
    bool ask(int i, int j) {                        // "? i j": is a[i] < a[j]?
        if (++used > limit) { cout << "Wrong Answer: more than " << limit << " questions\n"; exit(0); }
        return a[i] < a[j];
    }
};

void msort(Judge& J, vector<int>& idx, int l, int r) {   // sort positions by their hidden value
    if (r - l <= 1) return;
    int m = (l + r) / 2;
    msort(J, idx, l, m);
    msort(J, idx, m, r);
    vector<int> out;
    int i = l, j = m;
    while (i < m && j < r) out.push_back(J.ask(idx[i], idx[j]) ? idx[i++] : idx[j++]);
    while (i < m) out.push_back(idx[i++]);          // no questions for the leftovers
    while (j < r) out.push_back(idx[j++]);
    copy(out.begin(), out.end(), idx.begin() + l);
}

vector<int> guess(Judge& J) {
    vector<int> idx(J.n);
    iota(idx.begin(), idx.end(), 1);
    msort(J, idx, 0, J.n);
    vector<int> a(J.n + 1);
    for (int k = 0; k < J.n; k++) a[idx[k]] = k + 1; // the k-th smallest position holds k + 1
    return a;
}

int main() {
    mt19937 gen(84);
    int most = 0;
    for (int it = 1; it <= 300; it++) {
        Judge J;
        J.n = it <= 3 ? it : it == 4 ? 1000 : gen() % 1000 + 1;   // n = 1, 2, 3 and 1000 first
        J.limit = 9000;
        J.a.resize(J.n + 1);
        iota(J.a.begin() + 1, J.a.end(), 1);
        shuffle(J.a.begin() + 1, J.a.end(), gen);
        if (guess(J) != J.a) { cout << "wrong on test " << it; return 0; }
        if (J.n == 1000) most = max(most, J.used);
    }
    cout << "all 300 permutations found, n = 1000 used at most " << most << " questions";
}
all 300 permutations found, n = 1000 used at most 8727 questions

3. A judge that lies at most once. Guess the Price again (< / >=), but the judge may lie on one reply. At most 61 questions.

Solution

Ask every question twice. One lie can't fake both copies, so if they agree, the reply is true. If they disagree, the lie has just been spent: ask a third time (that reply is true), and from now on ask each question once. At most 2 · 30 + 1 = 61 questions. The local judge lies on question number lie; the stress test tries every position 0 (no lie) … 61 for 2000 prices.

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

struct Judge {                                      // may lie on question number `lie` (0 = never)
    ll x;
    int used = 0, lie = 0;
    string ask(ll y) {
        if (++used > 61) { cout << "Wrong Answer: more than 61 questions\n"; exit(0); }
        bool truth = x >= y;
        if (used == lie) truth = !truth;            // the one lie
        return truth ? ">=" : "<";
    }
};

ll solve(Judge& J) {
    ll lo = 1, hi = 1000000000;
    bool lied = false;                              // once the lie is spent, every reply is true
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        string r = J.ask(mid);
        if (!lied) {
            string r2 = J.ask(mid);                 // ask twice: one lie can't fake both
            if (r2 != r) { lied = true; r = J.ask(mid); }   // they disagree: the third reply is the truth
        }
        if (r == ">=") lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

int main() {
    mt19937 gen(84);
    int most = 0, runs = 0;
    for (int t = 0; t < 2000; t++) {
        ll x = t < 2 ? (t == 0 ? 1 : 1000000000) : gen() % 1000000000 + 1;
        for (int lie = 0; lie <= 61; lie++) {       // the lie on every possible question
            Judge J;
            J.x = x;
            J.lie = lie;
            if (solve(J) != x) { cout << "wrong for x = " << x << ", lie at " << lie; return 0; }
            most = max(most, J.used);
            runs++;
        }
    }
    cout << "all " << runs << " games won, at most " << most << " questions";
}
all 124000 games won, at most 61 questions

4. The max and the second max with few comparisons. n different hidden values; ? i j asks "is a[i] > a[j]?". Find the positions of the largest and the second largest with at most n + ⌈log2 n⌉ − 2 comparisons.

Solution

A knockout tournament finds the max in n − 1 comparisons (every match knocks out one player). The second max lost only to the champion, so it is among the at most ⌈log2 n⌉ players the champion beat (one per round): ⌈log2 n⌉ − 1 more comparisons. Total n + ⌈log2 n⌉ − 2.

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

struct Judge {                                      // hidden different values a[0..n-1]
    vector<int> a;
    int used = 0;
    bool bigger(int i, int j) { used++; return a[i] > a[j]; }   // "? i j": is a[i] > a[j]?
};

pair<int, int> top2(Judge& J, int n) {              // positions of the max and the second max
    vector<vector<int>> beat(n);                    // beat[w] = everyone w knocked out
    vector<int> round(n);
    iota(round.begin(), round.end(), 0);
    while (round.size() > 1) {                      // a knockout tournament: n - 1 matches
        vector<int> next;
        for (size_t k = 0; k + 1 < round.size(); k += 2) {
            int u = round[k], v = round[k + 1];
            int w = J.bigger(u, v) ? u : v, l = u ^ v ^ w;
            beat[w].push_back(l);
            next.push_back(w);
        }
        if (round.size() % 2) next.push_back(round.back());   // a bye
        round = next;
    }
    int champ = round[0];
    int second = beat[champ][0];                    // the second max lost only to the champion
    for (size_t k = 1; k < beat[champ].size(); k++)
        if (J.bigger(beat[champ][k], second)) second = beat[champ][k];
    return {champ, second};
}

int main() {
    mt19937 gen(84);
    for (int n = 2; n <= 2000; n++) {
        Judge J;
        J.a.resize(n);
        iota(J.a.begin(), J.a.end(), 1);
        shuffle(J.a.begin(), J.a.end(), gen);
        auto [m1, m2] = top2(J, n);
        int lg = 0;
        while ((1 << lg) < n) lg++;                 // ceil(log2 n)
        if (J.a[m1] != n || J.a[m2] != n - 1 || J.used > n + lg - 2) { cout << "failed for n = " << n; return 0; }
    }
    Judge J;
    J.a.resize(1000);
    iota(J.a.begin(), J.a.end(), 1);
    shuffle(J.a.begin(), J.a.end(), gen);
    top2(J, 1000);
    cout << "n = 2..2000 all correct, within n + ceil(log2 n) - 2; n = 1000 used " << J.used << " comparisons";
}
n = 2..2000 all correct, within n + ceil(log2 n) - 2; n = 1000 used 1008 comparisons

For n = 1000: 1000 + 10 − 2 = 1008, exactly the bound.

Quick quiz

// hidden x in [1, 10^6], replies "<" or ">="
// binary search: how many questions in the worst case?

A) 19 · B) 20 · C) 21 · D) 1000

Answer

B. 2^19 = 524288 < 10^6 ≤ 2^20 = 1048576, so 20 halvings are needed.

Interview questions

  1. What is an interactive problem? The judge holds hidden data and answers your questions one at a time; your next question may depend on its replies. The input is not fixed in advance.
  2. How do you test one at home? Write a local judge: a struct in the same file (fast, easy to stress test), or a separate interactor program connected by pipes (the real setup).
  3. What does the query limit tell you? The algorithm: 30 for 10^9 is one binary search; 2·log2 n means two questions per halving.
  4. Why mid = (lo + hi + 1) / 2? With lo = mid in one branch, rounding down can leave the range unchanged when hi = lo + 1; rounding up always shrinks it.
  5. What is flushing, and why does it matter here? Output is buffered; a flush writes the buffer out now. A question still in the buffer never reaches the judge, both sides wait: Idleness Limit Exceeded.
  6. endl vs "\n"? endl is "\n" plus a flush. Use "\n" for big outputs, endl (or cout.flush()) in interactive problems.
  7. What does cin.tie(nullptr) change? It unties cin from cout, so reading no longer flushes cout first. Fast for normal problems, a trap for interactive ones.
  8. What is an adaptive judge? One that chooses its replies (keeping them consistent) to make you use the most questions; solutions must be good in the worst case.
  9. How do you find a peak in O(log n) questions? Compare a[mid] with a[mid + 1] and keep the uphill side; there is always a peak there.

Glossary

Term Meaning Example
Interactive problem The judge answers your questions while your program runs Guess the Price
Interactor The judge's program that talks to yours interactor.py
Judge The system that runs your program and gives the verdict Accepted / Wrong Answer
Local judge A judge you write to test at home struct Judge
Protocol The exact format of questions, replies and the answer ? y, < / >=, ! x
Query (question) One line you print to ask the judge something ? 500000001
Query limit The most questions you may ask 30, 40
Hidden value Data only the judge can see x, the array a
stdout Standard output: where your program prints cout
stdin Standard input: where your program reads cin
Pipe A one-way channel from one program's output to another's input two pipes per game
Output buffer Memory where output waits before it is written out the letter in your bag
Flush Writing the buffer out now cout.flush()
endl A newline plus a flush cout << "? " << mid << endl;
fflush(stdout) Flush for printf C style
flush=True Flush for Python's print print("?", mid, flush=True)
cin.tie The stream cin flushes before reading (cout by default) cin.tie(nullptr) removes it
Fast-I/O template sync_with_stdio(false) + cin.tie(nullptr) from episode 2
Idleness Limit Exceeded Verdict: your program waited without printing both sides waiting
-1 reply The judge's "bad question, I've stopped" exit at once
Adaptive judge Chooses replies against you, staying consistent always keeps the bigger half
Binary search Halve the range with each question 30 for 10^9
Local maximum / peak A value bigger than both neighbours (−∞ outside) index 6 in 3 8 5 1 4 6 2
Stress test Many random tests against a checker all 1004 hidden prices found
Knockout tournament Pairwise matches, winners go on max in n − 1 comparisons

Summary

  • Interactive: print a question, flush, read the reply, repeat; print the answer; exit at once on -1.
  • Test with a local judge (a struct in the same file, plus stress tests) and, for the real setup, an interactor through pipes.
  • Read the query limit: 30 for 10^9 is binary search (mid = (lo + hi + 1) / 2 with lo = mid).
  • Flush every line: endl, cout.flush(), fflush(stdout), System.out.flush(), print(..., flush=True). cin.tie(nullptr) removes the automatic flush; a missing flush is Idleness Limit Exceeded.
  • Any peak: compare a[mid] with a[mid + 1], keep the uphill side; 2 questions per halving, 34 ≤ 40.

Solutions in C++, Java and Python

Every solution below was run against the interactor through two pipes.

Problem I1 · Guess the Price

C++

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

int main() {
    long long lo = 1, hi = 1000000000;           // x is somewhere in [lo, hi]
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        cout << "? " << mid << endl;             // endl = "\n" + flush
        string r;
        cin >> r;
        if (r == "-1") return 0;                 // the judge has stopped: exit at once
        if (r == ">=") lo = mid;
        else hi = mid - 1;
    }
    cout << "! " << lo << endl;
}

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        long lo = 1, hi = 1000000000;                 // x is somewhere in [lo, hi]
        while (lo < hi) {
            long mid = (lo + hi + 1) / 2;
            System.out.println("? " + mid);
            System.out.flush();                       // send the question now
            String r = in.readLine().trim();
            if (r.equals("-1")) return;               // the judge has stopped: exit at once
            if (r.equals(">=")) lo = mid;
            else hi = mid - 1;
        }
        System.out.println("! " + lo);
        System.out.flush();
    }
}

Python

lo, hi = 1, 10**9                    # x is somewhere in [lo, hi]
while lo < hi:
    mid = (lo + hi + 1) // 2
    print("?", mid, flush=True)      # send the question now
    r = input().strip()
    if r == "-1":                    # the judge has stopped: exit at once
        exit()
    if r == ">=":
        lo = mid
    else:
        hi = mid - 1
print("!", lo, flush=True)

Verdicts (all three languages, the same for each):

x = 500000000   Accepted in 30 questions
x = 1           Accepted in 29 questions
x = 1000000000  Accepted in 30 questions
adaptive        Accepted in 30 questions

Problem I2 · Find the Peak

C++

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

long long ask(int i) {                 // "? i", the judge replies a[i]
    cout << "? " << i << endl;         // endl flushes
    long long v;
    cin >> v;
    if (v == -1) exit(0);              // the judge has stopped: exit at once
    return v;
}

int main() {
    int n;
    cin >> n;
    int lo = 1, hi = n;                // a peak is in [lo, hi]
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (ask(mid) < ask(mid + 1)) lo = mid + 1;   // uphill to the right
        else hi = mid;                               // downhill: a peak at mid or left
    }
    cout << "! " << lo << endl;
}

Java

import java.io.*;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    static long ask(int i) throws IOException {      // "? i", the judge replies a[i]
        System.out.println("? " + i);
        System.out.flush();
        long v = Long.parseLong(in.readLine().trim());
        if (v == -1) System.exit(0);                 // the judge has stopped: exit at once
        return v;
    }

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(in.readLine().trim());
        int lo = 1, hi = n;                          // a peak is in [lo, hi]
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (ask(mid) < ask(mid + 1)) lo = mid + 1;   // uphill to the right
            else hi = mid;                               // downhill: a peak at mid or left
        }
        System.out.println("! " + lo);
        System.out.flush();
    }
}

Python

import sys

def ask(i):                          # "? i", the judge replies a[i]
    print("?", i, flush=True)
    v = int(input())
    if v == -1:                      # the judge has stopped: exit at once
        sys.exit()
    return v

n = int(input())
lo, hi = 1, n                        # a peak is in [lo, hi]
while lo < hi:
    mid = (lo + hi) // 2
    if ask(mid) < ask(mid + 1):      # uphill to the right
        lo = mid + 1
    else:                            # downhill: a peak at mid or left
        hi = mid
print("!", lo, flush=True)

Verdicts (all three languages, the same for each):

sample 3 8 5 1 4 6 2     Accepted: index 6, 6 questions
n = 1                    Accepted: index 1, 0 questions
n = 2                    Accepted: index 1, 2 questions
n = 3                    Accepted: index 2, 4 questions
n = 100000 (seed 84)     Accepted: index 72896, 32 questions
n = 100000 (seed 7)      Accepted: index 74913, 32 questions