xx. Interactive and Output-Only Constructions

Two related settings: interactive problems, where you construct the answer by asking questions; and output-only or “any valid answer” problems, where a randomized or search-based construction plus a checker is acceptable.

Setting	Technique
find a hidden object with few queries	each query should split the remaining candidates (information bound $\lceil {\log }_2(\#\text{candidates})\rceil$)
comparisons only	tournament for the max ($n-1$), max and min together ($\lceil 3n/2\rceil -2$)
hidden permutation, pairwise queries	find values by pairs, keep one “unknown” candidate
adaptive judge	your strategy must work for every consistent answer: think of the judge as an adversary
output-only, large instances	local search, simulated annealing, randomized restarts, then verify
”any valid answer” with a random construction	random choice + checker in a loop; expected tries $1/\mathrm{Pr}[\text{success}]$

Hidden permutation with mod queries

Query $(i,j)$ returns $p_i\mathrm{mod}{p}_j$. Two queries on a pair reveal the smaller value: if $p_i<p_j$, then $p_i\mathrm{mod}{p}_j=p_i$ while $p_j\mathrm{mod}{p}_i<p_i$.

// hidden permutation, query(i, j) returns p_i mod p_j; 2 queries per step find a value
template<class Q> vector<int> guessPermutation(int n, Q query) {
    vector<int> p(n, 0); int cand = 0;             // cand: index whose value is still unknown (the current maximum candidate)
    for (int i = 1; i < n; i++) {
        int x = query(cand, i), y = query(i, cand);
        if (x > y) p[cand] = x, cand = i;          // p_cand < p_i, so p_cand mod p_i = p_cand
        else p[i] = y;
    }
    p[cand] = n;
    return p;
}

Proof: 2(n−1) queries recover the permutation

For distinct $x<y$: $x\mathrm{mod}y=x$ and $y\mathrm{mod}x<x$. So of the two answers the larger one is $\min (p_i,p_j)$, and it belongs to the index with the smaller value. Each step therefore determines one value and keeps the larger element as the candidate. After $n-1$ steps every value except the maximum is known, and the maximum is $n$. Tested with a local judge on random permutations up to $n=30$, counting queries.

See Interactive Problems for I/O, flushing and local judges, and Heuristic Optimization for output-only search.