Winning threshold The minimum worst-case number of comparisons for the attacker is:
Choose attacker when , and defender otherwise.
Attack: upper bound Find representatives of two distinct values , grouping equal positions along the way. Once three strictly ordered values have been identified, their middle representative must be . Every remaining position can then be classified with one comparison against it.
Before finding all three values, processed positions belong to the two groups . Process two new positions together, first comparing them.
Each pair costs at most three comparisons. A final unpaired position costs at most two. Since all three values occur, the third value must be found by the end.
Let be the number of equality comparisons before obtaining the first distinct representatives. The first positions cost comparisons. For , the total is at most . Finding the middle earlier only reduces the cost, since the remaining positions then cost one comparison each.
Defense: lower bound Use DSU to merge positions declared equal. A group is unclassified, low, or high. Maintain the invariant that every strict comparison points from low to high.
To have no unclassified groups and only two groups left, classifying all positions costs at least comparisons, while merging from groups to two requires another . These are different comparisons, totaling at least .
Before that many comparisons, two valid witnesses always exist. If there are unclassified positions and low/high groups, assign values to (low, high, unclassified) as either or . If no comparisons have occurred, choose any two different valid sequences. With no unclassified positions, at least one of the low/high sides has two groups. Fix the other side at its extreme value and choose either of two groups on the larger side to have value , with its other groups at their extreme value. Both witnesses preserve every equality and strict comparison.
Thus when , this strategy answers every query and produces two witnesses.
Judging and complexity The judge's defender follows this strategy until there are three groups and merging two groups of the same type would leave only two. It then gives these two groups a strict order, uniquely fixing all three values. Before this event, two witnesses always exist, so the interactor can reject unsupported guesses exactly. For a submitted defender, both final witnesses are checked against every recorded reply. Valid final witnesses also establish consistency of all earlier prefixes.
The attacker uses time and space. The defender uses time and space. The interactor stores data. All numerical computations fit signed 64-bit integers.
For subtask 1, enumerate the valid sequences among all sequences and perform memoized minimax search on sets of remaining sequences. The state count is exponential, but is small enough. Subtask 2 uses the strategies above.
Solution written by GPT6