What the opponent can force

Why this matters when you build with AI

An AI tool can write a solution to an interactive problem that looks right and passes the sample. The usual faults show up only against a real judge. The program asks more questions than the limit allows, because it was written for one hidden value and not for every answer the judge might give. It forgets to flush its output, so both programs wait forever. Or it finishes too early and guesses an answer it has not yet proved.

A judge that answers adversarially is the test that finds these faults. An adversarial judge picks each answer after it sees the question, and it keeps its answers consistent with at least one possible hidden value. A solution that survives this judge has a real guarantee. The rest of this lesson builds that test and the arguments behind it.

Some terms first. A worst-case guarantee is a result that holds whatever the opponent does. An invariant is a quantity that every move changes in a known way. A potential function is a number that every move lowers by a known amount, so the game cannot last longer than the starting value. An interactive problem is one where your program asks questions and reads answers from a judge. A query bound is the largest number of questions the program may ask.

What the opponent can force

Start with a plain question. If the opponent plays as badly as possible for you, what can it force? A strategy is a rule that tells you what to do given everything seen so far. A strategy guarantees a result when the result follows for every reply the opponent can make.

Here is a small example. Two players alternately remove 1 or 2 stones from a pile of 5. The player who takes the last stone wins. You move first. Your move is a strategy question: which first move forces a win? You can check it by hand. Taking 2 leaves 3, and from 3 the opponent can take 1 or 2, leaving 2 or 1, and you take the rest and win. Taking 1 leaves 4, and the opponent takes 1 and leaves 3 for you, which is a loss. So taking 2 is the move that forces the win, and the opponent cannot stop it.

Notice the method. You did not need the opponent to choose well or badly. You checked every reply. That is what a worst-case guarantee means.

Invariants: a quantity that moves in a known way

An invariant is a quantity that every move changes in a fixed way. The sorting game below shows one.

On a permutation p of the numbers 1 to n, a move swaps two neighbours when the left one is larger. The array is sorted when no such pair is left. The player who cannot move loses, so the last player to move wins.

Count the inversions of p: the pairs i < j with p[i] > p[j]. A neighbour swap of a bad pair changes only the relative order of those two values. Every other pair keeps its order. So the count drops by exactly one with each move. That is the invariant: each move changes the inversion count by exactly one.

Work through p = (3, 2, 1), which has 3 inversions. Its two possible first moves give:

Swap the first two: (2, 3, 1), which has 2 inversions.
Swap the last two: (3, 1, 2), which has 2 inversions.

Both replies leave 2 inversions, and each move drops the count by one, so every game from (3, 2, 1) lasts exactly 3 moves. The first player makes moves 1 and 3, and so the first player makes the last move and wins. The sorted array has 0 inversions, which is an even count, and the player to move there loses. So the outcome is set by the parity of the starting count: when the count is odd, the first player wins, and when it is even, the first player loses.

The argument does not depend on which swap is chosen. Any legal first move leads to a position with one fewer inversion, so the parity flips each time, and the total number of moves is fixed. That is what it means for a strategy to guarantee a result: the result follows from the invariant, not from the choices.

Potential functions: bounding the length of a game

A potential function Phi is a number computed from a position with two properties. It is never negative, and every move lowers it by at least 1. If the start has Phi equal to P, then no play can last more than P moves, whatever the players choose.

The inversion count of the sorting game is a potential. It starts at inv(p), it stays at zero or above, and it drops by exactly one each move. So every play lasts at most inv(p) moves, and because the drop is exactly one, every play lasts exactly inv(p) moves.

A potential bounds work in an interactive problem as well. If each answer leaves at most half of the candidates, then after k answers about n / 2^k candidates remain. The solution needs one candidate to finish, so k must reach at least log2 n. The next two sections use this idea.

The sorting game is small enough to check by running it. This Python sample checks every permutation of up to 5 values against the parity rule, and it prints the example from above:

Python · editable

from functools import lru_cache
from itertools import permutations

def inversions(p):
    return sum(1 for i in range(len(p)) for j in range(i + 1, len(p)) if p[i] > p[j])

@lru_cache(maxsize=None)
def play_lengths(p):
    """(shortest, longest) number of moves from p until the array is sorted."""
    moves = [i for i in range(len(p) - 1) if p[i] > p[i + 1]]
    if not moves:
        return (0, 0)
    lows, highs = [], []
    for i in moves:
        q = list(p)
        q[i], q[i + 1] = q[i + 1], q[i]
        lo, hi = play_lengths(tuple(q))
        lows.append(lo + 1)
        highs.append(hi + 1)
    return (min(lows), max(highs))

@lru_cache(maxsize=None)
def first_wins(p):
    """True when the player to move wins under normal play."""
    for i in range(len(p) - 1):
        if p[i] > p[i + 1]:
            q = list(p)
            q[i], q[i + 1] = q[i + 1], q[i]
            if not first_wins(tuple(q)):
                return True
    return False

for n in range(2, 6):
    bad = 0
    for p in permutations(range(1, n + 1)):
        inv = inversions(p)
        if play_lengths(p) != (inv, inv) or first_wins(p) != (inv % 2 == 1):
            bad += 1
    print(f"n={n} permutations={len(list(permutations(range(1, n + 1))))} mismatches={bad}")

p = (3, 1, 2)
print("example p =", p, "inversions =", inversions(p), "lengths =", play_lengths(p),
      "first player wins =", first_wins(p))

Real output of that program, run with Python 3.14.4:

n=2 permutations=2 mismatches=0
n=3 permutations=6 mismatches=0
n=4 permutations=24 mismatches=0
n=5 permutations=120 mismatches=0
example p = (3, 1, 2) inversions = 2 lengths = (2, 2) first player wins = False

Every play has the length of the inversion count, and the parity rule holds, for all 120 permutations of 5 values. The same check in C++ over every permutation of up to 7 values also found zero mismatches.

Adaptive adversaries and query bounds

An interactive problem gives the solution a query bound. The solution asks questions, the judge answers, and the solution must finish within the bound. Here is the problem used in the rest of this lesson.

A judge hides an integer x with 1 at most x at most n. The solution sends a question ? t with 1 at most t at most n. The judge answers YES if x <= t and NO otherwise. The solution ends with ! v, and it is correct when v equals x.

A fixed judge picks x at the start and never changes it. An adaptive judge may change its choice as the questions come in, so long as every answer agrees with at least one value that is still possible. An adversary is an adaptive judge that chooses answers to make the solution work as hard as it can.

The lower bound from the adversary

Here is an adversary that keeps the candidate set as large as possible. The candidates form an interval [lo, hi], which starts as [1, n]. When the solution asks ? t, the candidates split into two parts: the YES part with values at most t, and the NO part with values above t. The adversary keeps the larger part and gives that answer. Ties go to NO.

The larger part has at least half of the candidates, rounded up. So each question leaves at least ceil(s / 2) candidates, where s is the number before the question. After k questions at least ceil(n / 2^k) candidates remain. The solution can finish only when one candidate is left, which needs 2^k at least n. So every solution needs at least ceil(log2 n) questions against this adversary. This is a lower bound for every solution, not only for one.

The upper bound from binary search

Binary search asks about the middle of the candidate interval. It takes the half that still contains the answer. Its candidate set after each question is at most ceil(s / 2), the same size the adversary can keep. So after k questions there are at most ceil(n / 2^k) candidates, and binary search needs at most ceil(log2 n) questions. The two bounds match, so binary search is optimal for this problem.

Standard technique in C++17: binary search that flushes

This program is the standard solution. It keeps the candidate interval [lo, hi] and asks about the middle. Every question line is flushed, so the judge sees it at once.

#include <bits/stdc++.h>
using namespace std;
 
// Interactive protocol (judge and solution talk through standard input and output).
// The judge first sends n. The solution sends "? t" with 1 <= t <= n. The judge answers
// "YES" when the hidden x satisfies x <= t, and "NO" otherwise. The solution finishes with "! v".
// Every query line must be flushed, or the judge never sees it and both sides wait.
int main() {
    long long n;
    cin >> n;
    long long lo = 1, hi = n;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;  // same as (lo + hi) / 2 without overflow
        cout << "? " << mid << endl;        // endl flushes the line
        string ans;
        cin >> ans;
        if (ans == "YES") hi = mid;
        else lo = mid + 1;
    }
    cout << "! " << lo << endl;
    return 0;
}

The endl at the end of each question is the flush. Without it, the question may sit in a buffer, and the judge waits forever for it. The next section shows that exact failure.

Worked problem: Hidden value in at most 30 questions

The judge hides an integer x with 1 at most x at most n, where 1 <= n <= 10^9. The judge may be adaptive, so its answers must agree with at least one value that is still possible. Your program may ask at most 30 questions. It must then send ! v with the value v that the judge's answers fix.

Why 30: 2^29 is 536,870,912, which is less than 10^9, and 2^30 is 1,073,741,824, which is at least 10^9. So ceil(log2 10^9) is 30, and the bound is exactly the number that binary search needs in the worst case.

Sample session, from a run of the adversary below with n = 5. The judge sends 5 first:

judge sends: 5
solver: ? 3   judge: YES
solver: ? 2   judge: YES
solver: ? 1   judge: NO
solver: ! 2   judge: AC

The solution asked 3 questions, which is ceil(log2 5). The session shows the adversary keeping the larger side each time: after ? 3 the candidates are [1, 3], after ? 2 they are [1, 2], and after ? 1 only 2 remains.

The solution

The solution is the program from the standard technique. It asks at most ceil(log2 n) questions for any n up to 10^9, which is at most 30, and it flushes each question.

How it was tested

The solution was run against the adversary below for every n from 1 to 300, using a driver that starts the solution as a separate process and talks to it through pipes. All 300 runs ended with AC, and every run stayed within ceil(log2 n) questions. The driver printed these numbers:

binary search vs adversary, n=1..300: all AC, every run within ceil(log2 n)
queries at n=10: 4  n=100: 7  n=300: 9
largest query count: 9 = ceil(log2 300) = 9

The solution was also run against a fixed judge for every value of x from 1 to n, for n from 1 to 40. That is 820 runs, and all 820 ended with AC within the limit. The most questions used by any run was 6, which is ceil(log2 40).

Complexity

Each test costs O(log n) time, which is at most 30 questions and about 30 steps of arithmetic. The memory is constant.

Writing an adaptive adversary

The adversary is the judge you write when a problem asks for a guarantee. The code below keeps the candidate interval and answers with the larger side. The driver code that runs it is in the hands-on section.

class Adversary:
    """Keeps the larger of the two possible sides of every answer, so the hidden value stays open."""
 
    def __init__(self, n):
        self.lo, self.hi = 1, n
 
    def answer(self, t):
        size = self.hi - self.lo + 1
        yes = max(0, min(t, self.hi) - self.lo + 1)  # candidates x with x <= t
        no = size - yes                               # candidates x with x > t
        if yes > no:
            self.hi = min(t, self.hi)
            return "YES"
        self.lo = max(t + 1, self.lo)
        return "NO"
 
    def finish(self, v):
        return "AC" if self.lo == self.hi == v else "WA"

Two lines matter most. The first is the choice if yes > no. It keeps the larger side, which is the rule the lower bound needs. The second is the claim that the candidate set never becomes empty. If no is zero, then yes is the whole candidate set and is larger than zero, so the YES branch runs. If yes is zero, the NO branch runs, and no is the whole set. So there is always at least one candidate left, and finish can judge the answer.

The same driver runs other strategies against this adversary. The linear strategy asks ? 1, ? 2 and so on until it gets YES. Its counts against the adversary were:

linear vs adversary n=5: AC, queries 4, ceil(log2 n) = 3
linear vs adversary n=10: AC, queries 9, ceil(log2 n) = 4
linear vs adversary n=30: AC, queries 29, ceil(log2 n) = 5

The linear strategy is correct every time, and it still breaks the limit. At n = 10^9 it would ask about a billion questions, far past the 30 allowed. The adversary is the test that shows this, and a fixed judge does not, because a fixed judge with a small x lets the linear strategy finish early.

Common mistakes

Missing flush. The first mistake is a question that never reaches the judge. The untied version below has cin.tie(nullptr) and no flush. It was run against a fixed judge with x = 7 and n = 10:

untied, no flush, n=10: ('TLE', 0)

The solution sent no question, and the driver stopped it after 3 seconds. Zero questions were seen. The default version, where cin is tied to cout, does not fail in this test:

tied (default), no flush, n=10: ('AC', 4)

Reading an answer flushes the output in the tied version, so the question gets out. Do not rely on that. Flush every question with endl or an explicit flush, and check the program against a driver that waits for each line.

Finishing early. A solution that prints an answer before it has narrowed the candidates is wrong. This one prints ! 1 at once and does not look at any answer:

solution that answers at once with '! 1' (n=10): ('WA', 0)

The judge rejects it, because the hidden value is not 1. The fix is to keep asking until the interval has one value, as the binary search does.

A strategy that works only on one judge. A fixed judge can make a bad strategy look fine. The linear strategy finished in 4 questions for n = 5 against the adversary, which is one more than the limit of 3. Test against the adversary, not only against fixed values, before you trust a count.

Asking outside the range. A question with t less than 1 or greater than n may be rejected by the judge. The driver stops a solution that does this and reports BAD_QUERY. A solution that sent ? 0 to a judge with n = 10 was stopped after one question with ('BAD_QUERY', 1). Check every t against the range before you send it.

Treating a random judge as a proof. A judge that answers at random does not give a lower bound. The lower bound needs the adversary's rule, which keeps the larger side, so that every answer leaves at least half the candidates.

Checklist to keep

Write down the state the solution must track, such as the candidate interval, and what each answer does to it.
Count the questions against the bound for the largest input, not for the sample.
Flush every question line, and do not rely on the input and output being tied.
Finish only when the candidate set has exactly one value.
Test against an adversarial judge, and against every fixed value for small n.
Use an invariant or potential function to bound the length of a game, and check it by brute force on small inputs.

Hands-on exercise

Work in your scratch folder. Write the binary search solution in the language you use for contests, and write the adversary above. Write a driver that starts the solution as a child process, reads each question, sends the adversary's answer, and counts the questions. Run it for n from 1 to 100.

Then write a second solution that asks questions from the top of the interval, ? n-1, ? n-2 and so on. Run it against the same adversary and print the largest question count. Compare that count with ceil(log2 n), and write one sentence on why the adversary forces the gap.

Prompt to try with an AI tool

Use this prompt, then check the answer with the steps above.

Write a C++17 solution for this interactive problem. The judge hides an integer x with
1 <= x <= n, where n is given first. Ask questions "? t" with 1 <= t <= n. The judge answers
YES when x <= t and NO otherwise. Finish with "! v". Use at most 30 questions for n up to 10^9.
Flush every question. Explain in two sentences why binary search needs at most ceil(log2 n)
questions. Then show the question sequence against a judge with x = 7 and n = 10.

A good answer uses the midpoint of the candidate interval, flushes each question, and gives the question sequence ? 5, ? 8, ? 7, ? 6 followed by ! 7. Check the flush and the sequence first. A common wrong answer asks ? 1, ? 2 and so on, which gives 7 questions for x = 7, and the linear strategy in the mistakes section shows the same fault.

Practice

These take a few minutes each. Try them on paper or in your scratch folder before you open the answers.

Practice 1: the lower bound for five values

Explain by hand why every solution needs 3 questions when n = 5, against the adversary.

Hint: After two questions, how many candidates can the adversary still keep?

Show the answer

Each question leaves at least ceil(s / 2) candidates, so from 5 the set is at least 3, then at least 2, then at least 1. After two questions the adversary can still keep 2 candidates. A solution that has asked only two questions cannot send ! with one value, so it must ask a third. Binary search with n = 5 also uses 3 questions in the sample session.

Practice 2: the winning first move in the sorting game

For p = (3, 2, 1) in the sorting game, which first moves lead to a position where the second player loses?

Hint: Count the inversions after each move. The second player loses when the count is even.

Show the answer

Both first moves win. Swapping the first two gives (2, 3, 1) with 2 inversions. Swapping the last two gives (3, 1, 2) with 2 inversions. In both cases the second player faces an even count, so the second player loses whatever it does. A check by a short search over all states confirms both moves are winning.

Practice 3: why the inversion count drops by exactly one

Explain why a swap of a bad adjacent pair lowers the inversion count by exactly one, and not by more.

Hint: Which pairs of values change their relative order when two neighbours swap?

Show the answer

Only the two swapped values change their relative order. For any other value, its position relative to both swapped values stays the same, so its inversions with them stay the same. The only pair whose order changes is the swapped pair itself, and it was an inversion, so the count drops by exactly one.

Practice 4: equal answers

Change the judge so that the answer to ? t is LESS, EQUAL or GREATER, and the solution finishes when it gets EQUAL. Explain why the lower bound of ceil(log2 n) still holds against an adversary that never answers EQUAL.

Hint: Count the candidates on each side of t when the answer is LESS or GREATER.

Show the answer

The adversary never answers EQUAL, so each answer is either LESS or GREATER, and the candidates split into two parts with no part removed. The argument from the lower bound applies unchanged: the larger part keeps at least half the candidates. So the solution still needs ceil(log2 n) questions against this adversary. A solution that gets EQUAL from a fixed judge can finish earlier, but the adversary never gives that chance.

Practice 5: the query bound for large inputs

How many questions does the binary search solution need in the worst case when n = 1000 and when n = 10^9?

Hint: Use ceil(log2 n), and check the power of two that is at least n.

Show the answer

2^10 is 1024, which is at least 1000, so ceil(log2 1000) is 10 questions. For n = 10^9, 2^29 is less than 10^9 and 2^30 is at least 10^9, so the worst case is 30 questions. That is the limit used in the worked problem, so binary search fits the limit exactly.

Summary

An opponent's guarantee is found by checking every reply, not by guessing what it will do. An invariant such as the inversion count changes in a known way each move, so it fixes the outcome by parity. A potential function bounds the length of any game. An adaptive adversary keeps the larger side of every answer, which forces at least ceil(log2 n) questions, and binary search meets that bound. Test a solution against the adversary as well as the fixed values, and flush every question.

Sources and scope

The inversion count, the invariant under adjacent swaps and the potential argument are standard arguments, and the adversary for binary search is the usual argument for a lower bound on comparison questions. The sorting game, the interactive problem and its adversary were written for this lesson. The sorting game was checked by exhaustive search for every permutation of up to 7 values, and the parity rule and the exact play length held for all of them. The interactive results come from a driver that ran the C++ and Python programs on this machine, with g++ 15.2.0 and Python 3.14.4 on Linux. The driver waited 5 seconds for each reply, and 3 seconds in the broken-protocol checks; these limits were chosen for the tests and are not a property of any judge. Other judges may use other limits and other protocols, so check the problem statement before you rely on these numbers.