Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 63 ยท Contest Toolkit

Interactive Problems

How interactive contest problems work: flushing, query limits, binary-search guessing and a local interactor you can test your solution against, with Python.

In an ordinary problem you read the whole input, compute, and print the answer. In an interactive problem the input does not exist yet. A program called the interactor (or grader) holds a hidden secret, and you discover it by asking questions: you print a query, the interactor prints a reply, you print another query, and so on until you announce the answer. The score depends on getting it right within a query limit.

These problems reward the same skills as binary search on the answer and careful reasoning, but they add two new failure modes: output that never reaches the judge, and too many questions. This lesson shows how to avoid both and how to test locally without a judge.

The conversation protocol

A typical statement says something like: "The hidden number x is between 1 and 10^6. You may ask at most 20 questions of the form ? m; the reply is <, = or > comparing m with x. Print ! x when you know it." Your side of the conversation has three rules.

  1. Flush after every line you print. When your output is connected to a pipe, Python buffers it, so the interactor may never see your query and both programs wait forever. That is an Idleness Limit Exceeded or time-limit verdict. Use print(..., flush=True).
  2. Read exactly what the statement says. One reply per query, in the stated format. If you read too much, you block; if you read too little, you fall out of step.
  3. Stop when told. Many problems send -1 after an invalid or excess query, and expect you to exit immediately.
sequenceDiagram
    participant Y as Your program
    participant I as Interactor
    Y->>I: ? 500000 (flushed)
    I-->>Y: >
    Y->>I: ? 250000 (flushed)
    I-->>Y: <
    Note over Y,I: ... at most 20 rounds ...
    Y->>I: ! 312345
    I-->>Y: verdict: accepted

Each query is a full round trip. If you forget to flush, the first arrow never leaves your machine.

Here is the skeleton you will reuse. It is read-only because the sandbox on this page has no judge to talk to:

Python
import sys

def ask(m):
    print("?", m, flush=True)       # flush: the interactor must see it now
    reply = sys.stdin.readline().strip()
    if reply == "-1":               # judge says we broke a rule
        sys.exit(0)
    return reply

lo, hi = 1, 10**6
while lo < hi:
    mid = (lo + hi) // 2
    reply = ask(mid)
    if reply == "=":
        lo = hi = mid
    elif reply == "<":              # mid < x
        lo = mid + 1
    else:
        hi = mid - 1
print("!", lo, flush=True)

Two small habits help. Define ask once so the flush can never be forgotten, and avoid printing debug text to standard output, because the interactor would read it as a query. Debug output belongs on sys.stderr.

How many queries do you really need?

The limit is a hint about the intended solution. Twenty queries for a range of 10^6 is the signature of binary search, since ceil(log2(10^6)) = 20. If the limit were about 2 * log2(n), expect a solution that asks two questions per halving, like ternary search. If it is n + 10 for an array of n elements, expect a linear scan with a clever trick.

Always compute the worst case by hand before coding: a loop that halves a range of N values needs ceil(log2(N)) queries when the final answer must be identified, and one fewer if you stop when the interval has size 1 without confirming. Off-by-one here costs a wrong answer on the largest test only.

Testing locally with a fake interactor

You do not need the judge to test. Write the interactor as a Python class that holds the secret, counts the queries and refuses to answer past the limit. Make your solution a function that receives the ask callable. Then the same function runs against the fake, and in a real contest you only swap ask for the printing version.

Python Guess the number with a query counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop returns the secret whenever the reply is =, and otherwise shrinks the interval. The random test confirms the worst case never exceeds 20 queries. The last block shows what a violation looks like: the fake interactor raises an exception, which is far easier to see than a silent "Wrong answer on test 7".

Adaptive interactors and a second example

Some interactors are adaptive: they do not fix the secret in advance, and answer in the way that is worst for you while staying consistent with earlier replies. Your solution must work for every consistent answer, which is the same as saying it must work in the worst case. You can imitate this locally by writing an adversary that keeps the set of still-possible secrets and always picks the reply that leaves the larger set.

As a second task, suppose the hidden object is a permutation of 1..n; a query ? i j returns whether p[i] < p[j]. Find the position of the maximum using as few queries as possible. A tournament does it in exactly n - 1 comparisons: keep the best-so-far candidate and compare it with the next index.

Python Find the maximum with comparison queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions use n - 1 queries, which is optimal for finding a maximum with comparisons. When a limit is tighter than a natural method allows (for example 3n/2 to find both the maximum and the minimum), pairing elements first is the standard trick: compare each pair once, then the larger of each pair competes for the maximum and the smaller for the minimum.

Running against a real interactor

When a contest provides an interactor program, you can connect it to your solution with two pipes. A shell script is the simplest way:

Terminal
mkfifo to_solution to_interactor
python3 solution.py < to_solution > to_interactor &
python3 interactor.py < to_interactor > to_solution

Writing your own interactor.py that mirrors the fake class above is worth the ten minutes, because it lets you run thousands of random secrets and also check the edge cases: the smallest and largest secrets, n = 1, and the exact query limit.

Checklist before submitting

  • Every print that the interactor must see uses flush=True.
  • Nothing except the protocol goes to standard output.
  • You read the reply after every query, and you stop on -1.
  • The worst-case query count is at most the limit, including n = 1 and the endpoints.
  • If the interactor is adaptive, your strategy relies on no assumption about how the secret was chosen.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Your interactive solution prints a query but the judge reports a time limit. What is the most likely cause?

    Output to a pipe is buffered. Without flush=True both programs wait for each other, which the judge reports as a timeout or idleness limit.
  2. 2. A problem allows 20 queries to find a number between 1 and 10^6. What does that tell you?

    20 is the number of halvings needed to isolate one of 10^6 values, so the limit is a strong hint for binary search.
  3. 3. Where should debug messages go in an interactive problem?

    Anything on standard output is parsed by the interactor as part of the protocol. Standard error is ignored by it.
  4. 4. What is the point of writing a fake interactor class with a query counter?

    A local interactor automates random and edge-case testing, including the query limit, but it only tests the secrets you try.

Summary

  • An interactive problem hides the input behind an interactor; you print queries, read replies and finally print the answer.
  • Flush after every printed line, print nothing else to standard output, and stop when the judge sends -1.
  • The query limit points to the intended method: log2 n suggests binary search, n - 1 suggests a linear tournament.
  • Structure your solution as a function that takes ask, and test it against a fake interactor that counts queries and rejects violations.
  • Adaptive interactors answer in the worst way for you, so your solution must be correct for every consistent set of replies.

Next: PBDS and C++ Contest STL Tricks