DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

012

Back to problem

Editorial

Winning threshold The minimum worst-case number of comparisons for the attacker is:

Q(N)=⌈3N2⌉−2.Q(N)=\left\lceil\frac{3N}{2}\right\rceil-2.Q(N)=⌈23N​⌉−2.

Choose attacker when M≥Q(N)M\geq Q(N)M≥Q(N), and defender otherwise.

Attack: upper bound Find representatives of two distinct values L<HL<HL<H, grouping equal positions along the way. Once three strictly ordered values have been identified, their middle representative must be 111. Every remaining position can then be classified with one comparison against it.

Before finding all three values, processed positions belong to the two groups L<HL<HL<H. Process two new positions a,ba,ba,b together, first comparing them.

  • If a=ba=ba=b, treat them as one group and compare it with LLL and, if necessary, HHH. This uses at most three comparisons in total.
  • Otherwise rename them so a<ba<ba<b, and compare aaa with . If , the chain identifies the middle; compare with once more.

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 eee be the number of equality comparisons before obtaining the first distinct representatives. The first e+2e+2e+2 positions cost e+1e+1e+1 comparisons. For R=N−e−2R=N-e-2R=N, 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.

  • For two unclassified groups, declare them unequal and classify one low and one high.
  • Against a low group, declare an unclassified group greater and classify it high. Against a high group, do the symmetric operation.
  • Two different low groups, or two different high groups, are declared equal and merged.
  • Low is less than high. Positions already in the same group compare equal.

To have no unclassified groups and only two groups left, classifying all NNN positions costs at least ⌈N/2⌉\lceil N/2\rceil⌈N/2⌉ comparisons, while merging from NNN groups to two requires another N−2N-2N−2. These are different comparisons, totaling at least Q(N)Q(N).

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 (0,2,1)(0,2,1)(0,2,1) or (1,2,0)(1,2,0)(1,2,0). 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 111, with its other groups at their extreme value. Both witnesses preserve every equality and strict comparison.

Thus when M<Q(N)M<Q(N)M<Q(N), 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 O(N)O(N)O(N) time and space. The defender uses O((N+M)α(N))O((N+M)\alpha(N))O((N+M)α(N)) time and O(N)O(N)O(N) space. The interactor stores data. All numerical computations fit signed 64-bit integers.

For subtask 1, enumerate the valid sequences among all 3N3^N3N sequences and perform memoized minimax search on sets of remaining sequences. The state count is exponential, but N≤6N\leq6N≤6 is small enough. Subtask 2 uses the strategies above.

Solution written by GPT6

LLL
a<La<La<L
a<L<Ha<L<Ha<L<H
bbb
LLL
  • If a>La>La>L, the chain L<a<bL<a<bL<a<b identifies the middle; compare the old representative HHH with aaa once more.
  • If a=La=La=L, compare bbb with HHH. Equality joins the existing groups; inequality identifies all three values.
  • −
    e−
    2
    e+1+3⌊R/2⌋+2(R mod 2)≤Q(N)e+1+3\lfloor R/2\rfloor+2(R\bmod2)\leq Q(N)e+1+3⌊R/2⌋+2(Rmod2)≤Q(N)
    Q(N)
    O(N+M)O(N+M)
    O(N+M)