EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All ICPC entries
Competitive Programming

ICPC 2020 - H. QC QC

There are n 100 machines, strictly more than half of them are good, and in one round every machine may test at most one other machine while every machine is tested by at most one other machine. If the tester is good,...

Source sync Apr 19, 2026
Track ICPC
Year 2020
Files TeX, C++, statement assets
Folder competitive_programming/icpc/2020/H-qc-qc
ICPC2020TeXC++statement textstatement pdf
Source of truth

Source-first archive entry

This page is built from the copied files in competitive_programming/icpc/2020/H-qc-qc. Edit competitive_programming/icpc/2020/H-qc-qc/solution.tex to update the written solution and competitive_programming/icpc/2020/H-qc-qc/solution.cpp to update the implementation.

The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.

Raw TeX Raw C++ Meta JSON
Problem statement

Problem Statement

Copied statement text kept beside the solution archive for direct reference.

Raw text Statement PDF 
Problem H
                                              QC QC
                                   Time limit: 10 seconds
Innovative Computable Quality Control (ICQC) has developed a ground-breaking new machine for per-
forming, well, quality control. Thanks to its novel Deep Intelligence technology, an ICQC quality control
(QC) machine can automatically, with 100% accuracy, detect manufacturing errors in any machine in
existence, whether it is a coffee machine, an intergalactic space ship, or a quantum computer.
ICQC is now setting up its factory for producing these QC machines. Like any other manufacturing
process, some fraction of the produced machines will suffer from malfunctions and these need to be
found and discarded. Fortunately, ICQC has just the product for detecting malfunctioning machines!
Obviously, ICQC should not simply use a QC machine on itself, since a malfunctioning machine might
incorrectly classify itself as working correctly. Instead, ICQC will take each batch of n machines pro-
duced during a day and have them test each other overnight. In particular, during every hour of the night,
each of the n QC machines can run a check on one of the other QC machines, and simultaneously be
checked by one other QC machine.
If the machine running the check is correct, it will correctly report whether the tested machine is correct
or malfunctioning, but if the machine running the check is malfunctioning, it may report either result. If
a machine A is used to test a machine B multiple times it will return the same result every time, even if
machine A is malfunctioning. The exact testing schedule does not have to be fixed in advance, so the
choice of which machines should check which other machines during the second hour of the night may
be based on the result of the tests from the first hour, and so on.
ICQC are 100% confident that strictly more than a half of the n QC machines in each batch are working
correctly, but the night is only 12 hours long, so there is only time to do a small number of test rounds.
Can you help ICQC determine which QC machines are malfunctioning?
For example, consider Sample Interaction 1 below. After the fourth hour, every machine has tested
every other machine. For machine 1, only one other machine claimed that it was malfunctioning, and
if it was truly malfunctioning then at least 3 of the other machines would claim this. For machine 4,
only one other machine claims that it is working, which implies that machine 2 must be malfunctioning
since more than half of the machines are supposed to be working. Note that even though machine 4 is
malfunctioning, it still happened to produce the correct responses in these specific test rounds.

Interaction
The first line of input contains a single integer b (1 ≤ b ≤ 500), the number of batches to follow. Each
batch is independent. You should process each batch interactively, which means the input you receive
will depend on the previous output of your program.
The first line of input for each batch contains a single integer n (1 ≤ n ≤ 100), the number of QC
machines in the batch. The interaction then proceeds in rounds. In each round, your program can
schedule tests for the next hour, by writing a line of the form “test x1 x2 . . . xn ” indicating that each
machine i should run a test on machine xi . If xi = 0, then machine i is idle in that round and performs
no test. All positive numbers in the sequence must be distinct.
After writing this line, there will be a result to read from the input. The result is one line containing

a string of length n, having a ‘1’ in position i if machine i says that machine xi is working correctly, ‘0’
if machine i says that machine xi is malfunctioning, and ‘-’ (dash) if machine i was idle in the round.
When your program has determined which machines are malfunctioning, but no later than after 12
rounds of tests, it must write a line of the form “answer S” where S is a binary string of length n,
having a ‘1’ in position i if machine i is working correctly, and a ‘0’ if it is malfunctioning.
After writing the answer line, your program should start processing the next batch by reading its number
n. When all b batches have been processed, the interaction ends and your program should exit.
Notes on interactive judging:
   • The evaluation is non-adversarial, meaning that the result of each machine testing each other
      machine is chosen in advance rather than in response to your queries.
   • Do not forget to flush output buffers after writing. See the Addendum to Judging Notes for details.
   • You are provided with a command-line tool for local testing, together with input files correspond-
      ing to the sample interactions. The tool has comments at the top to explain its use.

 Read                                    Sample Interaction 1                                      Write
 1
 5
                                               test 5 4 2 1 3
 11011
                                               test 4 5 1 3 2
 00110
                                               test 2 3 4 5 1
 01011
                                               test 3 1 5 2 4
 10100
                                               answer 10101

 Read                                    Sample Interaction 2                                      Write
 2
 4
                                               test 2 3 4 1
 1111
                                               answer 1111
 7
                                               test 2 3 4 5 6 7 1
 0001100
                                               test 0 0 0 0 2 4 0
 ----11-
                                               answer 0101110
Editorial

Editorial

Rendered from the copied solution.tex file. The original TeX source remains available below.

Raw TeX

Key Observations

  • If two machines test each other and the result is 11, then they are in the same state: either both are good or both are bad. A mixed pair can never produce 11.

  • Therefore we can repeatedly merge homogeneous groups: groups whose machines are known to all have the same state, although we do not yet know whether that common state is good or bad.

  • If two homogeneous groups of the same size are compared through one representative from each side:

    • 11 means the two groups have the same state and can be merged.

    • 10 or 01 already certifies one entire side as bad.

    • 00 only tells us that the two groups are not both good.

    • After this repeated pairing process, the unresolved part has a very rigid form:

      • leftover homogeneous groups of pairwise different sizes $1,2,4,\dots$,

      • plus pairs of equal-sized homogeneous groups with at most one good side.

      • Let $L$ be the largest leftover group. Since the sum of all smaller leftover sizes is $< |L|$, if $L$ were bad then the total number of bad machines would already be at least the number of good machines. Hence $L$ must be good.

      • Once every leftover group is classified using $L$, let \[ G = \text{total size of good leftovers}, \qquad B = \text{total size of bad leftovers}. \] Every unresolved pair contributes either $0$ surplus (one good, one bad) or $-2w$ surplus (both bad, size $w$). Since the global surplus is positive, \[ G - B - 2Y > 0, \] where $Y$ is the total size of still-unresolved pairs that are actually ``both bad''. So \[ Y \le \left\lfloor \frac{G-B-1}{2} \right\rfloor . \] This number is the only global uncertainty we still need.

      Phase 1: Build The Structured State

      Start from singleton homogeneous groups.

      In one round, pair the current active groups arbitrarily. If one group is left unpaired, it becomes a leftover. For every paired active groups $A,B$:

      • ask one representative of $A$ to test one representative of $B$ and vice versa,

      • if the answer is 11, merge $A$ and $B$ into one active homogeneous group of doubled size,

      • otherwise remove this comparison from the active process and store it as an unresolved pair:

        • type $O$: one side is already known bad (10 or 01),

        • type $U$: neither side is oriented yet (00).

        The number of active groups at least halves every round, so this phase uses at most $6$ rounds for $n \le 100$.

        Phase 2: Classify Leftovers

        Take the largest leftover group $L$; by the observation above it is good.

        Because the leftover sizes are distinct powers of two, if $|L| = 2^k$ then there are at most $k$ other leftover groups, hence fewer than $|L|$ of them. We use distinct machines from $L$ to test one representative of every other leftover group in one additional round, so all leftover groups become fully known.

        After this round we know $G$ and $B$, and we obtain the valid upper bound \[ Y_{\max} = \left\lfloor \frac{G-B-1}{2} \right\rfloor \] for the remaining ``both bad'' pairs.

        Phase 3: Exact Minimax On The Pair Game

        Compressed State

        All machines outside the unresolved pairs are already known. For the remaining pairs, only the following information matters:

        • good: how many known-good machines we currently have available as truthful testers,

        • budget: the current upper bound on the total size of unresolved pairs that may still be ``both bad'',

        • for every size $w \in \{1,2,4,8,16,32,64\}$:

          • $U_w$: number of unresolved unoriented pairs of size $w$,

          • $O_w$: number of unresolved oriented pairs of size $w$.

          This compressed state is enough because every same-sized pair is symmetric: once only the common size is known, the future interaction depends only on how many pairs of that size we act on, not on their identities.

          Easy Inference

          If $w > \texttt{budget}$, then a size-$w$ oriented pair cannot be ``both bad'', so its unknown side must already be good. We may therefore mark all such $O_w$ pairs as solved immediately, adding $w$ good machines for each of them.

          Allowed Actions

          In one round, using only known-good testers, for every size $w$ we may choose:

          • prep on some $U_w$ pairs: test one chosen side,

          • finishU on some $U_w$ pairs: test both sides,

          • finishO on some $O_w$ pairs: test the unknown side.

          • The total tester cost is \[ \sum_w (\texttt{prep}_w + 2\cdot \texttt{finishU}_w + \texttt{finishO}_w) \] and must not exceed good.

          Worst-Case Transition

          For the minimax search we intentionally use a pessimistic transition:

          • prep on a $U_w$ pair is treated as only converting that pair into an oriented $O_w$ pair. In reality it can be strictly better, because a good answer may solve the pair immediately.

          • finishU and finishO each solve one pair unless that pair spends $w$ units of the remaining bad-budget.

          • So after choosing an action, an adversary may distribute the current budget over the tested finishU/finishO pairs. If the adversary spends total weight $D$, then:

          • good increases by the total size of all finished pairs minus $D$,

          • budget decreases by $D$,

          • every prepared $U_w$ becomes one more $O_w$.

          • This adversary is stronger than the real judge because it is allowed to place the remaining bad budget on any tested finishing actions of matching total weight. Therefore, if our search wins against this stronger adversary, it also wins in the real problem.

          We run an exact memoized minimax on states \[ (\texttt{rounds\_left}, \texttt{good}, \texttt{budget}, (U_w), (O_w)). \]

          For a state, we enumerate all legal actions in the compressed game and check whether every legal adversarial budget-distribution leads to another winning state. The first such action is stored and replayed online.

          Because:

          • there are only $7$ possible sizes,

          • $n \le 100$,

          • $\texttt{budget} \le 49$,

          • $\texttt{rounds\_left} \le 12$,

          • the reachable compressed game graph is tiny, and the memoized search is easily fast enough.

          Correctness Proof

          We prove that the algorithm always outputs the correct classification within $12$ rounds.

          Lemma 1.

          Whenever two machines mutually return 11, they are in the same state.

          Proof.

          If one of them were good and the other bad, then the good machine would necessarily answer 0 when asked about the bad one. Hence a mixed pair cannot produce 11. So 11 implies either both are good or both are bad. □

          Lemma 2.

          After Phase 1, every active/leftover group is homogeneous, and every removed comparison is represented by either a $U$-pair or an $O$-pair of equal-sized homogeneous groups.

          Proof.

          Initially every singleton is homogeneous. By Lemma 1, a 11 comparison merges two homogeneous groups into a larger homogeneous group. Any non-11 comparison is removed from the active process and stored as a pair of the same size. The answers 10, 01, 00 mean respectively ``left side bad'', ``right side bad'', and ``not both good'', exactly matching the meanings of $O$ and $U$. □

          Lemma 3.

          The largest leftover group is good.

          Proof.

          Let its size be $W$. All other leftover groups have distinct smaller powers of two, so their total size is $< W$. Every unresolved pair contains at most half good machines. Therefore, if the largest leftover were bad, then outside that group we would have at most as many good machines as bad machines coming from pairs, and fewer than $W$ extra machines from the other leftovers. That would make the total number of bad machines at least the total number of good machines, contradicting the promise that strictly more than half are good. □

          Lemma 4.

          After classifying all leftovers, the total size $Y$ of unresolved pairs that are actually ``both bad'' satisfies \[ Y \le \left\lfloor \frac{G-B-1}{2} \right\rfloor . \]

          Proof.

          Every unresolved pair contributes either $0$ surplus (one good, one bad) or $-2w$ surplus (both bad, size $w$). The leftovers contribute surplus $G-B$. Since the total surplus is strictly positive, \[ G-B-2Y > 0. \] Rearranging gives the claimed bound. □

          Lemma 5.

          The compressed state used in Phase 3 contains all information needed for future worst-case play.

          Proof.

          Inside a homogeneous group, every member has the same hidden state. Hence when a truthful tester probes one representative, the answer determines the whole group. For future decisions, the identity of a pair matters only through:

          • its size,

          • whether it is oriented or not,

          • whether it may still belong to the remaining bad-budget.

          • The exact placement of that hidden bad-budget among equal-sized unresolved pairs is irrelevant once we quantify over all such placements in the minimax step. □

          Lemma 6.

          If the minimax search declares a compressed state winning, then the real interactive position represented by that state is also winning.

          Proof.

          The search uses a stronger adversary than the real judge:

          • every prep is pessimistically treated as never giving an immediate extra good machine,

          • the remaining bad-budget may be placed on any tested finishing actions of matching total weight.

          • Any real continuation is therefore one of the branches covered by the minimax search, or a strictly easier one. So an action that wins against the search adversary also wins in the real game. □

          Theorem.

          The algorithm always classifies every machine correctly within at most $12$ rounds.

          Proof.

          By Lemmas 1 and 2, Phase 1 constructs the stated structured decomposition in at most $6$ rounds. By Lemma 3, the largest leftover group is good, so one additional round classifies all other leftovers. By Lemma 4, this yields a valid initial bad-budget for the remaining pair game. By Lemmas 5 and 6, the memoized minimax in Phase 3 computes only winning actions and therefore resolves all remaining pairs within the remaining rounds. At that point every group status is known, so the final answer string is correct. □

          Complexity Analysis

          Phase 1 uses $O(n)$ queries per round and at most $6$ rounds. The pair endgame works on a compressed state with only $7$ sizes and performs a memoized minimax over the reachable compressed game graph. Since all parameters are bounded by small constants ($n \le 100$, at most $12$ rounds), this is effectively constant-time per batch, and easily within the limit in practice.

          Memory usage is $O(n)$ for storing groups plus the memoized compressed states.

          Implementation Notes

          • The code keeps the minimax intentionally pessimistic: prep on a $U$-pair is always modeled as only turning it into an $O$-pair, even though the real answer can immediately solve the pair.

          • Whenever the current bad-budget becomes smaller than a pair size $w$, every oriented pair of size $w$ is immediately certified good on the unknown side and removed without spending a round.

          • The local version in solution.cpp includes a simulator and random stress-checks; those were used to validate the compressed game model.

Source code

Code

Exact copied C++ implementation from solution.cpp.

C++ competitive_programming/icpc/2020/H-qc-qc/solution.cpp

Exact copied implementation source.

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

namespace {

const int UNKNOWN = 0;
const int GOOD = 1;
const int BAD = 2;
const int MAXN = 100;
const int SIZE_CNT = 7;
const int SIZES[SIZE_CNT] = {1, 2, 4, 8, 16, 32, 64};

int size_index(int sz) {
    for (int i = 0; i < SIZE_CNT; ++i) {
        if (SIZES[i] == sz) {
            return i;
        }
    }
    return -1;
}

struct Group {
    int sz;
    int status;
    vector<int> members;
};

struct UPair {
    int a;
    int b;
    int sz;
};

struct OPair {
    int bad;
    int unk;
    int sz;
};

struct Action {
    unsigned char prep[SIZE_CNT];
    unsigned char finish_u[SIZE_CNT];
    unsigned char finish_o[SIZE_CNT];

    Action() {
        memset(prep, 0, sizeof(prep));
        memset(finish_u, 0, sizeof(finish_u));
        memset(finish_o, 0, sizeof(finish_o));
    }
};

struct SearchState {
    unsigned char rounds_left;
    unsigned char bad_budget;
    unsigned char u[SIZE_CNT];
    unsigned char o[SIZE_CNT];
    unsigned short good;

    bool operator==(const SearchState& other) const {
        return rounds_left == other.rounds_left &&
               bad_budget == other.bad_budget &&
               good == other.good &&
               memcmp(u, other.u, sizeof(u)) == 0 &&
               memcmp(o, other.o, sizeof(o)) == 0;
    }
};

struct SearchStateHash {
    size_t operator()(const SearchState& st) const {
        size_t h = st.rounds_left;
        h = h * 239017 + st.bad_budget;
        h = h * 239017 + st.good;
        for (int i = 0; i < SIZE_CNT; ++i) {
            h = h * 239017 + st.u[i];
        }
        for (int i = 0; i < SIZE_CNT; ++i) {
            h = h * 239017 + st.o[i];
        }
        return h;
    }
};

struct MemoEntry {
    bool known;
    bool win;
    Action action;

    MemoEntry() : known(false), win(false), action() {}
};

struct SearchEngine {
    unordered_map<SearchState, MemoEntry, SearchStateHash> memo;

    SearchState normalize(SearchState st) const {
        int good = st.good;
        int y = st.bad_budget;
        for (int i = 0; i < SIZE_CNT; ++i) {
            if (SIZES[i] > y && st.o[i] != 0) {
                good += SIZES[i] * st.o[i];
                st.o[i] = 0;
            }
        }
        if (good > MAXN) {
            good = MAXN;
        }
        st.good = static_cast<unsigned short>(good);
        return st;
    }

    bool empty_pairs(const SearchState& st) const {
        for (int i = 0; i < SIZE_CNT; ++i) {
            if (st.u[i] != 0 || st.o[i] != 0) {
                return false;
            }
        }
        return true;
    }

    bool can_win(const SearchState& raw, Action* best_action = nullptr) {
        SearchState st = normalize(raw);
        if (empty_pairs(st)) {
            if (best_action != nullptr) {
                *best_action = Action();
            }
            return true;
        }
        if (st.rounds_left == 0) {
            return false;
        }
        unordered_map<SearchState, MemoEntry, SearchStateHash>::iterator it = memo.find(st);
        if (it != memo.end() && it->second.known) {
            if (best_action != nullptr && it->second.win) {
                *best_action = it->second.action;
            }
            return it->second.win;
        }

        MemoEntry entry;
        vector<int> difficult;
        vector<int> easy_desc;
        for (int i = 0; i < SIZE_CNT; ++i) {
            if (st.u[i] == 0 && st.o[i] == 0) {
                continue;
            }
            if (SIZES[i] <= st.bad_budget) {
                difficult.push_back(i);
            } else {
                easy_desc.push_back(i);
            }
        }
        sort(easy_desc.begin(), easy_desc.end(), greater<int>());

        Action cur;
        vector<Action> actions;
        const int max_actions = 6000;
        generate_actions(st, difficult, easy_desc, 0, st.good, cur, actions, max_actions);
        sort(actions.begin(), actions.end(), [&](const Action& lhs, const Action& rhs) {
            int lhs_used = action_cost(lhs);
            int rhs_used = action_cost(rhs);
            if (lhs_used != rhs_used) {
                return lhs_used > rhs_used;
            }
            int lhs_gain = optimistic_gain(lhs);
            int rhs_gain = optimistic_gain(rhs);
            return lhs_gain > rhs_gain;
        });

        for (size_t idx = 0; idx < actions.size(); ++idx) {
            const Action& act = actions[idx];
            if (action_cost(act) == 0) {
                continue;
            }
            vector<vector<int> > bad_options;
            vector<int> bad_cur(SIZE_CNT, 0);
            generate_bad_options(st, act, difficult, 0, st.bad_budget, bad_cur, bad_options);
            bool ok = true;
            for (size_t j = 0; j < bad_options.size(); ++j) {
                SearchState nxt = transition(st, act, bad_options[j]);
                nxt.rounds_left--;
                if (!can_win(nxt, nullptr)) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                entry.known = true;
                entry.win = true;
                entry.action = act;
                memo[st] = entry;
                if (best_action != nullptr) {
                    *best_action = act;
                }
                return true;
            }
        }

        entry.known = true;
        entry.win = false;
        memo[st] = entry;
        return false;
    }

    int action_cost(const Action& act) const {
        int total = 0;
        for (int i = 0; i < SIZE_CNT; ++i) {
            total += act.prep[i];
            total += 2 * act.finish_u[i];
            total += act.finish_o[i];
        }
        return total;
    }

    int optimistic_gain(const Action& act) const {
        int total = 0;
        for (int i = 0; i < SIZE_CNT; ++i) {
            total += SIZES[i] * (act.prep[i] + act.finish_u[i] + act.finish_o[i]);
        }
        return total;
    }

    void generate_actions(const SearchState& st, const vector<int>& difficult,
                          const vector<int>& easy_desc, int pos, int rem,
                          Action& cur, vector<Action>& out, int max_actions) const {
        if ((int)out.size() >= max_actions) {
            return;
        }
        if (pos == (int)difficult.size()) {
            Action done = cur;
            int leftover = rem;
            for (int i = 0; i < (int)easy_desc.size() && leftover > 0; ++i) {
                int idx = easy_desc[i];
                int take = min<int>(st.u[idx], leftover);
                done.prep[idx] = static_cast<unsigned char>(take);
                leftover -= take;
            }
            if (action_cost(done) > 0) {
                out.push_back(done);
            }
            return;
        }

        int idx = difficult[pos];
        int max_prep = min<int>(st.u[idx], rem);
        for (int prep = 0; prep <= max_prep; ++prep) {
            int max_finish_u = min<int>(st.u[idx] - prep, (rem - prep) / 2);
            for (int finish_u = 0; finish_u <= max_finish_u; ++finish_u) {
                int max_finish_o = min<int>(st.o[idx], rem - prep - 2 * finish_u);
                for (int finish_o = 0; finish_o <= max_finish_o; ++finish_o) {
                    cur.prep[idx] = static_cast<unsigned char>(prep);
                    cur.finish_u[idx] = static_cast<unsigned char>(finish_u);
                    cur.finish_o[idx] = static_cast<unsigned char>(finish_o);
                    generate_actions(st, difficult, easy_desc, pos + 1,
                                     rem - prep - 2 * finish_u - finish_o,
                                     cur, out, max_actions);
                    if ((int)out.size() >= max_actions) {
                        cur.prep[idx] = cur.finish_u[idx] = cur.finish_o[idx] = 0;
                        return;
                    }
                }
            }
        }
        cur.prep[idx] = cur.finish_u[idx] = cur.finish_o[idx] = 0;
    }

    void generate_bad_options(const SearchState& st, const Action& act,
                              const vector<int>& difficult, int pos, int rem_budget,
                              vector<int>& cur, vector<vector<int> >& out) const {
        if (pos == (int)difficult.size()) {
            out.push_back(cur);
            return;
        }
        int idx = difficult[pos];
        int cnt = act.finish_u[idx] + act.finish_o[idx];
        int w = SIZES[idx];
        int mx = min<int>(cnt, rem_budget / w);
        for (int bad = 0; bad <= mx; ++bad) {
            cur[idx] = bad;
            generate_bad_options(st, act, difficult, pos + 1, rem_budget - bad * w, cur, out);
        }
        cur[idx] = 0;
    }

    SearchState transition(const SearchState& st, const Action& act,
                           const vector<int>& bad_per_size) const {
        SearchState nxt = st;
        int gain = 0;
        int bad_cost = 0;
        for (int i = 0; i < SIZE_CNT; ++i) {
            int prep = act.prep[i];
            int finish_u = act.finish_u[i];
            int finish_o = act.finish_o[i];
            int bad = bad_per_size[i];
            nxt.u[i] = static_cast<unsigned char>(nxt.u[i] - prep - finish_u);
            nxt.o[i] = static_cast<unsigned char>(nxt.o[i] + prep - finish_o);
            gain += SIZES[i] * (finish_u + finish_o - bad);
            bad_cost += SIZES[i] * bad;
        }
        int good = min<int>(MAXN, st.good + gain);
        int budget = st.bad_budget - bad_cost;
        if (budget < 0) {
            budget = 0;
        }
        nxt.good = static_cast<unsigned short>(good);
        nxt.bad_budget = static_cast<unsigned char>(budget);
        return nxt;
    }
};

struct Solver {
    int n;
    int rounds_used;
    vector<Group> groups;
    vector<UPair> upairs;
    vector<OPair> opairs;
    vector<int> leftovers;
    vector<int> good_pool;
    int bad_budget;
    SearchEngine engine;

#ifdef LOCAL
    vector<int> hidden_good;
    vector<vector<int> > hidden_ans;
#endif

    Solver() : n(0), rounds_used(0), groups(1), upairs(), opairs(),
               leftovers(), good_pool(), bad_budget(0), engine() {}

    int add_group(const vector<int>& members, int status = UNKNOWN) {
        Group g;
        g.sz = (int)members.size();
        g.status = status;
        g.members = members;
        groups.push_back(g);
        return (int)groups.size() - 1;
    }

    int add_singleton(int x) {
        vector<int> v(1, x);
        return add_group(v, UNKNOWN);
    }

    int merge_groups(int a, int b) {
        vector<int> merged = groups[a].members;
        merged.insert(merged.end(), groups[b].members.begin(), groups[b].members.end());
        return add_group(merged, UNKNOWN);
    }

    void mark_good(int gid) {
        if (groups[gid].status == GOOD) {
            return;
        }
        groups[gid].status = GOOD;
        for (int i = 0; i < (int)groups[gid].members.size(); ++i) {
            good_pool.push_back(groups[gid].members[i]);
        }
    }

    void mark_bad(int gid) {
        groups[gid].status = BAD;
    }

    int representative(int gid) const {
        return groups[gid].members[0];
    }

    string ask_round(const vector<int>& to) {
        vector<int> used_to(n + 1, 0);
        vector<int> used_from(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            if (to[i] == 0) {
                continue;
            }
            used_from[i]++;
            used_to[to[i]]++;
            if (to[i] == i) {
                throw runtime_error("self-test is forbidden");
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (used_from[i] > 1 || used_to[i] > 1) {
                throw runtime_error("invalid round schedule");
            }
        }
        rounds_used++;
        if (rounds_used > 12) {
            throw runtime_error("used more than 12 rounds");
        }
#ifdef LOCAL
        string ret(n, '-');
        for (int i = 1; i <= n; ++i) {
            if (to[i] != 0) {
                ret[i - 1] = char('0' + hidden_ans[i][to[i]]);
            }
        }
        return ret;
#else
        cout << "test";
        for (int i = 1; i <= n; ++i) {
            cout << ' ' << to[i];
        }
        cout << '\n';
        cout.flush();
        string ret;
        cin >> ret;
        return ret;
#endif
    }

    void send_answer() {
        string ans(n, '0');
        for (int gid = 1; gid < (int)groups.size(); ++gid) {
            if (groups[gid].status == GOOD) {
                for (int x : groups[gid].members) {
                    ans[x - 1] = '1';
                }
            }
        }
#ifdef LOCAL
        for (int i = 1; i <= n; ++i) {
            if ((ans[i - 1] == '1') != (hidden_good[i] == 1)) {
                cerr << "answer=" << ans << '\n';
                throw runtime_error("wrong answer");
            }
        }
#else
        cout << "answer " << ans << '\n';
        cout.flush();
#endif
    }

    void normalize_easy_oriented() {
        bool changed = true;
        while (changed) {
            changed = false;
            vector<OPair> kept;
            for (int i = 0; i < (int)opairs.size(); ++i) {
                if (opairs[i].sz > bad_budget) {
                    mark_bad(opairs[i].bad);
                    mark_good(opairs[i].unk);
                    changed = true;
                } else {
                    kept.push_back(opairs[i]);
                }
            }
            opairs.swap(kept);
        }
    }

    SearchState build_state(int rounds_left) {
        SearchState st;
        st.rounds_left = static_cast<unsigned char>(rounds_left);
        st.bad_budget = static_cast<unsigned char>(max(0, bad_budget));
        st.good = static_cast<unsigned short>(min<int>(MAXN, (int)good_pool.size()));
        memset(st.u, 0, sizeof(st.u));
        memset(st.o, 0, sizeof(st.o));
        for (int i = 0; i < (int)upairs.size(); ++i) {
            int idx = size_index(upairs[i].sz);
            st.u[idx]++;
        }
        for (int i = 0; i < (int)opairs.size(); ++i) {
            int idx = size_index(opairs[i].sz);
            st.o[idx]++;
        }
        return st;
    }

    void phase_one() {
        vector<int> active;
        for (int i = 1; i <= n; ++i) {
            active.push_back(add_singleton(i));
        }

        while ((int)active.size() >= 2) {
            vector<int> next_active;
            vector<pair<int, int> > pairs;
            vector<int> to(n + 1, 0);
            int m = (int)active.size();
            if (m % 2 == 1) {
                leftovers.push_back(active.back());
                active.pop_back();
            }
            for (int i = 0; i < (int)active.size(); i += 2) {
                int a = active[i];
                int b = active[i + 1];
                pairs.push_back(make_pair(a, b));
                to[representative(a)] = representative(b);
                to[representative(b)] = representative(a);
            }
            string ret = ask_round(to);
            for (int i = 0; i < (int)pairs.size(); ++i) {
                int a = pairs[i].first;
                int b = pairs[i].second;
                int ra = ret[representative(a) - 1] - '0';
                int rb = ret[representative(b) - 1] - '0';
                if (ra == 1 && rb == 1) {
                    next_active.push_back(merge_groups(a, b));
                } else if (ra == 1 && rb == 0) {
                    OPair p;
                    p.bad = a;
                    p.unk = b;
                    p.sz = groups[a].sz;
                    opairs.push_back(p);
                } else if (ra == 0 && rb == 1) {
                    OPair p;
                    p.bad = b;
                    p.unk = a;
                    p.sz = groups[a].sz;
                    opairs.push_back(p);
                } else {
                    UPair p;
                    p.a = a;
                    p.b = b;
                    p.sz = groups[a].sz;
                    upairs.push_back(p);
                }
            }
            active.swap(next_active);
        }
        if (!active.empty()) {
            leftovers.push_back(active[0]);
        }
    }

    void initialize_pair_game() {
        if (leftovers.empty()) {
            throw runtime_error("there must be a leftover good group");
        }
        int best = leftovers[0];
        for (int i = 1; i < (int)leftovers.size(); ++i) {
            if (groups[leftovers[i]].sz > groups[best].sz) {
                best = leftovers[i];
            }
        }
        vector<int> reordered;
        int other_sum = 0;
        reordered.push_back(best);
        for (int gid : leftovers) {
            if (gid != best) {
                reordered.push_back(gid);
                other_sum += groups[gid].sz;
            }
        }
        if (!(groups[best].sz > other_sum)) {
            throw runtime_error("largest leftover must dominate the rest");
        }
        mark_good(best);
        leftovers.swap(reordered);
        classify_other_leftovers();
        int good_sum = 0;
        int bad_sum = 0;
        for (int gid : leftovers) {
            if (groups[gid].status == GOOD) {
                good_sum += groups[gid].sz;
            } else if (groups[gid].status == BAD) {
                bad_sum += groups[gid].sz;
            } else {
                throw runtime_error("all leftovers must be classified before pair game");
            }
        }
        if (good_sum <= bad_sum) {
            throw runtime_error("classified leftovers must have a strict good majority");
        }
        bad_budget = (good_sum - bad_sum - 1) / 2;
        normalize_easy_oriented();
    }

    vector<int> take_good_testers(int need) {
        if ((int)good_pool.size() < need) {
            throw runtime_error("not enough good testers");
        }
        vector<int> testers;
        testers.reserve(need);
        for (int i = 0; i < need; ++i) {
            testers.push_back(good_pool[i]);
        }
        return testers;
    }

    void execute_pair_action(const Action& act) {
        vector<vector<int> > up_by_size(SIZE_CNT), op_by_size(SIZE_CNT);
        for (int i = 0; i < (int)upairs.size(); ++i) {
            up_by_size[size_index(upairs[i].sz)].push_back(i);
        }
        for (int i = 0; i < (int)opairs.size(); ++i) {
            op_by_size[size_index(opairs[i].sz)].push_back(i);
        }

        int need = 0;
        for (int i = 0; i < SIZE_CNT; ++i) {
            need += act.prep[i];
            need += 2 * act.finish_u[i];
            need += act.finish_o[i];
        }
        vector<int> testers = take_good_testers(need);
        int ptr = 0;
        vector<int> to(n + 1, 0);

        struct PrepTask {
            int pair_idx;
            bool is_u;
            int group_a;
            int group_b;
            int tester;
            int sz;
        };
        struct FinishUTask {
            int pair_idx;
            int group_a;
            int group_b;
            int tester_a;
            int tester_b;
            int sz;
        };
        struct FinishOTask {
            int pair_idx;
            int bad_gid;
            int unk_gid;
            int tester;
            int sz;
        };

        vector<PrepTask> prep_tasks;
        vector<FinishUTask> finish_u_tasks;
        vector<FinishOTask> finish_o_tasks;
        vector<int> used_u(upairs.size(), 0), used_o(opairs.size(), 0);

        for (int idx = 0; idx < SIZE_CNT; ++idx) {
            for (int k = 0; k < act.prep[idx]; ++k) {
                int pair_idx = up_by_size[idx][k];
                used_u[pair_idx] = 1;
                PrepTask task;
                task.pair_idx = pair_idx;
                task.is_u = true;
                task.group_a = upairs[pair_idx].a;
                task.group_b = upairs[pair_idx].b;
                task.sz = upairs[pair_idx].sz;
                task.tester = testers[ptr++];
                to[task.tester] = representative(task.group_a);
                prep_tasks.push_back(task);
            }
            for (int k = 0; k < act.finish_u[idx]; ++k) {
                int pair_idx = up_by_size[idx][act.prep[idx] + k];
                used_u[pair_idx] = 1;
                FinishUTask task;
                task.pair_idx = pair_idx;
                task.group_a = upairs[pair_idx].a;
                task.group_b = upairs[pair_idx].b;
                task.sz = upairs[pair_idx].sz;
                task.tester_a = testers[ptr++];
                task.tester_b = testers[ptr++];
                to[task.tester_a] = representative(task.group_a);
                to[task.tester_b] = representative(task.group_b);
                finish_u_tasks.push_back(task);
            }
            for (int k = 0; k < act.finish_o[idx]; ++k) {
                int pair_idx = op_by_size[idx][k];
                used_o[pair_idx] = 1;
                FinishOTask task;
                task.pair_idx = pair_idx;
                task.bad_gid = opairs[pair_idx].bad;
                task.unk_gid = opairs[pair_idx].unk;
                task.sz = opairs[pair_idx].sz;
                task.tester = testers[ptr++];
                to[task.tester] = representative(task.unk_gid);
                finish_o_tasks.push_back(task);
            }
        }

        string ret = ask_round(to);

        vector<UPair> next_u;
        vector<OPair> next_o;
        for (int i = 0; i < (int)upairs.size(); ++i) {
            if (!used_u[i]) {
                next_u.push_back(upairs[i]);
            }
        }
        for (int i = 0; i < (int)opairs.size(); ++i) {
            if (!used_o[i]) {
                next_o.push_back(opairs[i]);
            }
        }

        for (const PrepTask& task : prep_tasks) {
            int r = ret[task.tester - 1] - '0';
            if (r == 1) {
                mark_good(task.group_a);
                mark_bad(task.group_b);
            } else {
                mark_bad(task.group_a);
                OPair p;
                p.bad = task.group_a;
                p.unk = task.group_b;
                p.sz = task.sz;
                next_o.push_back(p);
            }
        }

        for (const FinishUTask& task : finish_u_tasks) {
            int ra = ret[task.tester_a - 1] - '0';
            int rb = ret[task.tester_b - 1] - '0';
            if (ra == 1 && rb == 0) {
                mark_good(task.group_a);
                mark_bad(task.group_b);
            } else if (ra == 0 && rb == 1) {
                mark_good(task.group_b);
                mark_bad(task.group_a);
            } else if (ra == 0 && rb == 0) {
                mark_bad(task.group_a);
                mark_bad(task.group_b);
                bad_budget -= task.sz;
                if (bad_budget < 0) {
                    bad_budget = 0;
                }
            } else {
                throw runtime_error("double-check on a U-pair returned 11");
            }
        }

        for (const FinishOTask& task : finish_o_tasks) {
            int r = ret[task.tester - 1] - '0';
            mark_bad(task.bad_gid);
            if (r == 1) {
                mark_good(task.unk_gid);
            } else {
                mark_bad(task.unk_gid);
                bad_budget -= task.sz;
                if (bad_budget < 0) {
                    bad_budget = 0;
                }
            }
        }

        upairs.swap(next_u);
        opairs.swap(next_o);
        normalize_easy_oriented();
    }

    void classify_other_leftovers() {
        vector<int> unknown_leftovers;
        for (int gid : leftovers) {
            if (groups[gid].status == UNKNOWN) {
                unknown_leftovers.push_back(gid);
            }
        }
        if (unknown_leftovers.empty()) {
            return;
        }
        vector<int> testers = take_good_testers((int)unknown_leftovers.size());
        vector<int> to(n + 1, 0);
        for (int i = 0; i < (int)unknown_leftovers.size(); ++i) {
            to[testers[i]] = representative(unknown_leftovers[i]);
        }
        string ret = ask_round(to);
        for (int i = 0; i < (int)unknown_leftovers.size(); ++i) {
            if (ret[testers[i] - 1] == '1') {
                mark_good(unknown_leftovers[i]);
            } else {
                mark_bad(unknown_leftovers[i]);
            }
        }
    }

    void solve_case() {
        phase_one();
        initialize_pair_game();
        while (!upairs.empty() || !opairs.empty()) {
            int rounds_left = 12 - rounds_used;
            SearchState st = build_state(rounds_left);
            Action act;
            if (!engine.can_win(st, &act)) {
                throw runtime_error("no winning action found for the compressed state");
            }
            execute_pair_action(act);
        }
        send_answer();
    }
};

#ifdef LOCAL
mt19937 rng(1234567);

Solver build_random_solver(int n) {
    Solver solver;
    solver.n = n;
    solver.hidden_good.assign(n + 1, 0);
    int good_cnt = 0;
    while (good_cnt * 2 <= n) {
        good_cnt = 0;
        for (int i = 1; i <= n; ++i) {
            solver.hidden_good[i] = int(rng() & 1);
            good_cnt += solver.hidden_good[i];
        }
    }
    solver.hidden_ans.assign(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) {
                continue;
            }
            if (solver.hidden_good[i]) {
                solver.hidden_ans[i][j] = solver.hidden_good[j];
            } else {
                solver.hidden_ans[i][j] = int(rng() & 1);
            }
        }
    }
    return solver;
}
#endif

void solve() {
#ifdef LOCAL
    for (int n = 1; n <= 100; ++n) {
        for (int it = 0; it < 200; ++it) {
            Solver solver = build_random_solver(n);
            try {
                solver.solve_case();
            } catch (const exception& e) {
                cerr << "fail n=" << n << " it=" << it
                     << " rounds=" << solver.rounds_used
                     << " budget=" << solver.bad_budget << '\n';
                cerr << "hidden:";
                for (int i = 1; i <= n; ++i) {
                    cerr << solver.hidden_good[i];
                }
                cerr << '\n';
                for (int i = 1; i <= n; ++i) {
                    cerr << "row" << i << ':';
                    for (int j = 1; j <= n; ++j) {
                        if (i == j) {
                            cerr << '-';
                        } else {
                            cerr << solver.hidden_ans[i][j];
                        }
                    }
                    cerr << '\n';
                }
                throw;
            }
        }
    }
    cerr << "local-random-ok\n";
#else
    int batches;
    cin >> batches;
    while (batches--) {
        Solver solver;
        cin >> solver.n;
        solver.solve_case();
    }
#endif
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Source files

Source Files

Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.

TeX write-up competitive_programming/icpc/2020/H-qc-qc/solution.tex

Exact copied write-up source.

Raw file 
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2020\\H. QC QC}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

There are $n \le 100$ machines, strictly more than half of them are good, and in one round every machine may test at most one other machine while every machine is tested by at most one other machine.

If the tester is good, the answer is correct. If the tester is bad, the answer is arbitrary but fixed for that ordered pair.

We must determine the status of every machine in at most $12$ rounds.

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item If two machines test each other and the result is \texttt{11}, then they are in the same state: either both are good or both are bad. A mixed pair can never produce \texttt{11}.
    \item Therefore we can repeatedly merge \emph{homogeneous groups}: groups whose machines are known to all have the same state, although we do not yet know whether that common state is good or bad.
    \item If two homogeneous groups of the same size are compared through one representative from each side:
    \begin{itemize}[leftmargin=*]
        \item \texttt{11} means the two groups have the same state and can be merged.
        \item \texttt{10} or \texttt{01} already certifies one entire side as bad.
        \item \texttt{00} only tells us that the two groups are not both good.
    \end{itemize}
    \item After this repeated pairing process, the unresolved part has a very rigid form:
    \begin{itemize}[leftmargin=*]
        \item leftover homogeneous groups of pairwise different sizes $1,2,4,\dots$,
        \item plus pairs of equal-sized homogeneous groups with at most one good side.
    \end{itemize}
    \item Let $L$ be the largest leftover group. Since the sum of all smaller leftover sizes is $< |L|$, if $L$ were bad then the total number of bad machines would already be at least the number of good machines. Hence $L$ must be good.
    \item Once every leftover group is classified using $L$, let
    \[
        G = \text{total size of good leftovers}, \qquad
        B = \text{total size of bad leftovers}.
    \]
    Every unresolved pair contributes either $0$ surplus (one good, one bad) or $-2w$ surplus (both bad, size $w$). Since the global surplus is positive,
    \[
        G - B - 2Y > 0,
    \]
    where $Y$ is the total size of still-unresolved pairs that are actually ``both bad''. So
    \[
        Y \le \left\lfloor \frac{G-B-1}{2} \right\rfloor .
    \]
    This number is the only global uncertainty we still need.
\end{itemize}

\section*{Phase 1: Build The Structured State}

Start from singleton homogeneous groups.

In one round, pair the current active groups arbitrarily. If one group is left unpaired, it becomes a leftover. For every paired active groups $A,B$:

\begin{itemize}[leftmargin=*]
    \item ask one representative of $A$ to test one representative of $B$ and vice versa,
    \item if the answer is \texttt{11}, merge $A$ and $B$ into one active homogeneous group of doubled size,
    \item otherwise remove this comparison from the active process and store it as an unresolved pair:
    \begin{itemize}[leftmargin=*]
        \item type $O$: one side is already known bad (\texttt{10} or \texttt{01}),
        \item type $U$: neither side is oriented yet (\texttt{00}).
    \end{itemize}
\end{itemize}

The number of active groups at least halves every round, so this phase uses at most $6$ rounds for $n \le 100$.

\section*{Phase 2: Classify Leftovers}

Take the largest leftover group $L$; by the observation above it is good.

Because the leftover sizes are distinct powers of two, if $|L| = 2^k$ then there are at most $k$ other leftover groups, hence fewer than $|L|$ of them. We use distinct machines from $L$ to test one representative of every other leftover group in one additional round, so all leftover groups become fully known.

After this round we know $G$ and $B$, and we obtain the valid upper bound
\[
    Y_{\max} = \left\lfloor \frac{G-B-1}{2} \right\rfloor
\]
for the remaining ``both bad'' pairs.

\section*{Phase 3: Exact Minimax On The Pair Game}

\subsection*{Compressed State}

All machines outside the unresolved pairs are already known. For the remaining pairs, only the following information matters:

\begin{itemize}[leftmargin=*]
    \item \texttt{good}: how many known-good machines we currently have available as truthful testers,
    \item \texttt{budget}: the current upper bound on the total size of unresolved pairs that may still be ``both bad'',
    \item for every size $w \in \{1,2,4,8,16,32,64\}$:
    \begin{itemize}[leftmargin=*]
        \item $U_w$: number of unresolved unoriented pairs of size $w$,
        \item $O_w$: number of unresolved oriented pairs of size $w$.
    \end{itemize}
\end{itemize}

This compressed state is enough because every same-sized pair is symmetric: once only the common size is known, the future interaction depends only on how many pairs of that size we act on, not on their identities.

\subsection*{Easy Inference}

If $w > \texttt{budget}$, then a size-$w$ oriented pair cannot be ``both bad'', so its unknown side must already be good. We may therefore mark all such $O_w$ pairs as solved immediately, adding $w$ good machines for each of them.

\subsection*{Allowed Actions}

In one round, using only known-good testers, for every size $w$ we may choose:

\begin{itemize}[leftmargin=*]
    \item \texttt{prep} on some $U_w$ pairs: test one chosen side,
    \item \texttt{finishU} on some $U_w$ pairs: test both sides,
    \item \texttt{finishO} on some $O_w$ pairs: test the unknown side.
\end{itemize}

The total tester cost is
\[
    \sum_w (\texttt{prep}_w + 2\cdot \texttt{finishU}_w + \texttt{finishO}_w)
\]
and must not exceed \texttt{good}.

\subsection*{Worst-Case Transition}

For the minimax search we intentionally use a \emph{pessimistic} transition:

\begin{itemize}[leftmargin=*]
    \item \texttt{prep} on a $U_w$ pair is treated as only converting that pair into an oriented $O_w$ pair. In reality it can be strictly better, because a good answer may solve the pair immediately.
    \item \texttt{finishU} and \texttt{finishO} each solve one pair unless that pair spends $w$ units of the remaining bad-budget.
\end{itemize}

So after choosing an action, an adversary may distribute the current budget over the tested \texttt{finishU}/\texttt{finishO} pairs. If the adversary spends total weight $D$, then:

\begin{itemize}[leftmargin=*]
    \item \texttt{good} increases by the total size of all finished pairs minus $D$,
    \item \texttt{budget} decreases by $D$,
    \item every prepared $U_w$ becomes one more $O_w$.
\end{itemize}

This adversary is \emph{stronger} than the real judge because it is allowed to place the remaining bad budget on any tested finishing actions of matching total weight. Therefore, if our search wins against this stronger adversary, it also wins in the real problem.

\subsection*{Memoized Search}

We run an exact memoized minimax on states
\[
    (\texttt{rounds\_left}, \texttt{good}, \texttt{budget}, (U_w), (O_w)).
\]

For a state, we enumerate all legal actions in the compressed game and check whether \emph{every} legal adversarial budget-distribution leads to another winning state. The first such action is stored and replayed online.

Because:

\begin{itemize}[leftmargin=*]
    \item there are only $7$ possible sizes,
    \item $n \le 100$,
    \item $\texttt{budget} \le 49$,
    \item $\texttt{rounds\_left} \le 12$,
\end{itemize}

the reachable compressed game graph is tiny, and the memoized search is easily fast enough.

\section*{Correctness Proof}

We prove that the algorithm always outputs the correct classification within $12$ rounds.

\paragraph{Lemma 1.}
Whenever two machines mutually return \texttt{11}, they are in the same state.

\paragraph{Proof.}
If one of them were good and the other bad, then the good machine would necessarily answer \texttt{0} when asked about the bad one. Hence a mixed pair cannot produce \texttt{11}. So \texttt{11} implies either both are good or both are bad. \qed

\paragraph{Lemma 2.}
After Phase 1, every active/leftover group is homogeneous, and every removed comparison is represented by either a $U$-pair or an $O$-pair of equal-sized homogeneous groups.

\paragraph{Proof.}
Initially every singleton is homogeneous. By Lemma 1, a \texttt{11} comparison merges two homogeneous groups into a larger homogeneous group. Any non-\texttt{11} comparison is removed from the active process and stored as a pair of the same size. The answers \texttt{10}, \texttt{01}, \texttt{00} mean respectively ``left side bad'', ``right side bad'', and ``not both good'', exactly matching the meanings of $O$ and $U$. \qed

\paragraph{Lemma 3.}
The largest leftover group is good.

\paragraph{Proof.}
Let its size be $W$. All other leftover groups have distinct smaller powers of two, so their total size is $< W$. Every unresolved pair contains at most half good machines. Therefore, if the largest leftover were bad, then outside that group we would have at most as many good machines as bad machines coming from pairs, and fewer than $W$ extra machines from the other leftovers. That would make the total number of bad machines at least the total number of good machines, contradicting the promise that strictly more than half are good. \qed

\paragraph{Lemma 4.}
After classifying all leftovers, the total size $Y$ of unresolved pairs that are actually ``both bad'' satisfies
\[
Y \le \left\lfloor \frac{G-B-1}{2} \right\rfloor .
\]

\paragraph{Proof.}
Every unresolved pair contributes either $0$ surplus (one good, one bad) or $-2w$ surplus (both bad, size $w$). The leftovers contribute surplus $G-B$. Since the total surplus is strictly positive,
\[
G-B-2Y > 0.
\]
Rearranging gives the claimed bound. \qed

\paragraph{Lemma 5.}
The compressed state used in Phase 3 contains all information needed for future worst-case play.

\paragraph{Proof.}
Inside a homogeneous group, every member has the same hidden state. Hence when a truthful tester probes one representative, the answer determines the whole group. For future decisions, the identity of a pair matters only through:
\begin{itemize}[leftmargin=*]
    \item its size,
    \item whether it is oriented or not,
    \item whether it may still belong to the remaining bad-budget.
\end{itemize}
The exact placement of that hidden bad-budget among equal-sized unresolved pairs is irrelevant once we quantify over \emph{all} such placements in the minimax step. \qed

\paragraph{Lemma 6.}
If the minimax search declares a compressed state winning, then the real interactive position represented by that state is also winning.

\paragraph{Proof.}
The search uses a stronger adversary than the real judge:
\begin{itemize}[leftmargin=*]
    \item every \texttt{prep} is pessimistically treated as never giving an immediate extra good machine,
    \item the remaining bad-budget may be placed on any tested finishing actions of matching total weight.
\end{itemize}
Any real continuation is therefore one of the branches covered by the minimax search, or a strictly easier one. So an action that wins against the search adversary also wins in the real game. \qed

\paragraph{Theorem.}
The algorithm always classifies every machine correctly within at most $12$ rounds.

\paragraph{Proof.}
By Lemmas 1 and 2, Phase 1 constructs the stated structured decomposition in at most $6$ rounds. By Lemma 3, the largest leftover group is good, so one additional round classifies all other leftovers. By Lemma 4, this yields a valid initial bad-budget for the remaining pair game. By Lemmas 5 and 6, the memoized minimax in Phase 3 computes only winning actions and therefore resolves all remaining pairs within the remaining rounds. At that point every group status is known, so the final answer string is correct. \qed

\section*{Complexity Analysis}

Phase 1 uses $O(n)$ queries per round and at most $6$ rounds. The pair endgame works on a compressed state with only $7$ sizes and performs a memoized minimax over the reachable compressed game graph. Since all parameters are bounded by small constants ($n \le 100$, at most $12$ rounds), this is effectively constant-time per batch, and easily within the limit in practice.

Memory usage is $O(n)$ for storing groups plus the memoized compressed states.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item The code keeps the minimax intentionally pessimistic: \texttt{prep} on a $U$-pair is always modeled as only turning it into an $O$-pair, even though the real answer can immediately solve the pair.
    \item Whenever the current bad-budget becomes smaller than a pair size $w$, every oriented pair of size $w$ is immediately certified good on the unknown side and removed without spending a round.
    \item The local version in \texttt{solution.cpp} includes a simulator and random stress-checks; those were used to validate the compressed game model.
\end{itemize}

\end{document}