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
-1and 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 setslo = mid. Withlo = 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) / 2really givesWrong Answer: more than 30 questionsfor x = 500000000 and for x = 1 (the local judge stops the endless loop), andAccepted in 29 questionsfor x = 7: a bug that hides on some inputs. (The rule: if a branch keepsmidon 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, andmid + 1 ≤ hialways 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
- 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.
- 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).
- 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.
- Why
mid = (lo + hi + 1) / 2? Withlo = midin one branch, rounding down can leave the range unchanged when hi = lo + 1; rounding up always shrinks it. - 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.
endlvs"\n"?endlis"\n"plus a flush. Use"\n"for big outputs,endl(orcout.flush()) in interactive problems.- What does
cin.tie(nullptr)change? It untiescinfromcout, so reading no longer flushescoutfirst. Fast for normal problems, a trap for interactive ones. - 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.
- 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) / 2withlo = 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