Unique Values

To get a feel for the problem, let's set up a small example to play with, say $n = 4$:

array:  1 2 3 2 1 4 3 1 4      special value 1, at positions 1, 5, 8
index:  1 2 3 4 5 6 7 8 9

The first thing to look at: what happens if you query a set $S$ and then query its complement, as in everything that's not in $S$?

For any of the paired values, one of three things is true:

• Both copies are in $S$. Then they're a pair inside $S$, so they contribute $0$ to that query, and they don't appear in the complement at all, so they contribute $0$ there too.
• Both copies are outside $S$. Then they don't appear in $S$ at all, so they contribute $0$ there, and they form a pair in the complement, which also contributes $0$.
• The pair is split, one copy on each side. Then it shows up as a singleton in $S$, contributing $1$, and it also shows up as a singleton in the complement, contributing $1$ over there.

So in every case, a paired value contributes exactly the same amount to both queries. The special value is where it gets interesting:

• One copy in $S$, two out: a singleton inside ($+1$), and a pair outside ($0$).
• Two copies in, one out: a pair inside ($0$), and a singleton outside ($+1$).
• All three in, or all three out: all three copies sit on one side, where they count for nothing, and the other side has none of them. $0$ to both.

So how do we tell three apart from zero? Let's write out some queries on the example and look.

S (indices)      values in S     answer   |S|    parities?
{1,5,8}          1 1 1           0        3      differ (even vs odd)
{2,1,5,8}        2 1 1 1         1        4      differ
{2,4,1,5,8}      2 2 1 1 1       0        5      differ
{2,3}            2 3             2        2      match
{1,2}            1 2             2        2      match
{1,5,2}          1 1 2           1        3      match

So when the answer for both queries is the same, we can use the parity to tell whether it's all three or none. Putting it all together:

Written out as pseudo-code:

count(S):                        # how many special positions are in S
    a = query(S)
    b = query(everything not in S)
    if a == b + 1: return 1
    if b == a + 1: return 2
    # a == b: zero or three -- decide by parity
    return 3 if (a mod 2) != (|S| mod 2) else 0

This felt really powerful, but I didn't really know what to do with it yet.

Since counting is now easy (Key Observation 1: two queries tell us exactly how many special positions are in any set), here's an idea: find the smallest region that contains at least one special position, and shrink it to pinpoint one exactly.

There are $2n + 1 \leq 2001$ positions, so each binary search takes about $\log_2 2001 \approx 11$ steps, and each step costs two queries. That's $22$ queries per special position, $66$ in total, which fits in the budget for B1.

# count(S) is the two-query counter from Idea 1
 
for t = 1, 2, 3:
    binary search the smallest i in [1, 2n+1] with count({1..i}) >= t
    the t-th special position is that i

Accepted for B1 (my submission). But $66$ queries is double the budget for B2, so we need something better.

I kept going back to a bit-by-bit idea. The positions are $11$-bit numbers, so what if, for each bit $d$, I figure out which of the three special positions have bit $d$ on?

The query for that: take the set of all indices with bit $d$ on, plus its complement, and use the counter from Idea 1. If the count is $3$, all three positions have the bit on. If it's $0$, all three have it off. Otherwise the bit splits them, and now you're into case analysis about which item has which bit.

Working from the most significant bit down, you can treat the three items as sorted while you discover them, filling in a little grid of bits with three columns and $11$ rows. As long as every bit comes out $0$-or-$3$, the three items are still indistinguishable from each other, so on the first split there is nothing to figure out: assign the bits in sorted order, for free.

count() per bit, filling the grid from the most significant bit down:
 
           item1  item2  item3    count   what happens
bit 10:      0      0      0        0     all off; still indistinguishable
bit  9:      1      1      1        3     all on; still indistinguishable
bit  8:      0      0      1        1     first split: assign in sorted order
                                          for free; item 3 is now distinct
bit  7:      ?      ?      ?        1     ambiguous: the lone 1 could be on
                                          item 3, or on one of items 1, 2

That last row is the problem. Once some item is distinguished, a split bit no longer assigns itself: we have to find out which group the lone $1$ belongs to, and that takes one more count(). The trick for the extra query is to use the known bit-prefixes: in the grid above, item 3 is the only item whose bits so far are $011$, so a query restricted to indices starting with $011$ is guaranteed not to contain items 1 and 2.

extra count() on { indices with bits 10..8 = 011, bit 7 = 1 }:
    1  ->  item 3 has bit 7 = 1; items 1 and 2 get 0 0
           (those two are still indistinguishable from each other)
    0  ->  item 3 has bit 7 = 0; one of items 1, 2 has the 1, and those
           two are still interchangeable, so assign in sorted order for
           free: they get 0 1 -- and now all three items are distinct

So it's a little state machine: at each bit, the three items are either all still indistinguishable, or one is distinguished from the other two, or all three are distinct, and the state decides whether a split bit assigns itself for free or costs an extra count(). I convinced myself that some variant of this works out to at most four queries per bit: $44$ in total. I'll admit I never wrote it out fully.

But $44$ is still not $33$. And it was clear that any solution leaning on count() automatically pays two queries for each thing it learns, which really eats up the budget. I got stuck here.

array:  1 2 3 2 1 4 3 1 4      special value 1, at positions 1, 5, 8
index:  1 2 3 4 5 6 7 8 9
 
S (indices)      values in S     answer
{2}              2               1
{2,4}            2 2             0       down by 1 (completed a pair)
{2,4,1}          2 2 1           1       up by 1 (new singleton)
{2,4,1,5}        2 2 1 1         0       down by 1 (completed a pair)
{2,4,1,5,8}      2 2 1 1 1       0       unchanged!

I'll note that at this point I didn't know how to use this, but it felt very worthwhile.

The other thing to try is going back to the case analysis we already have from Idea 1.

Go through the branches of count(). The first two, where the answers differ by one, genuinely compare the two answers, so they need both queries. But look at the last branch: to separate three from zero, it checks the parity of the answer against the parity of $|S|$, and $|S|$ is something we already know without asking the judge.

Let's check that against the $+1 / -1 / 0$ behavior. Start from the empty set: the answer is $0$ and the size is $0$, so the parities match. Now add items one at a time. Each addition grows the size by exactly $1$ and moves the answer by $+1$ or $-1$, so both parities flip together and stay in sync. The only way they can fall out of sync is an addition that leaves the answer alone, and we just saw there is exactly one of those: the third copy of the special value. And once that happens, the $\pm 1$ tracking picks right back up, so the mismatch never repairs itself.

In all the other cases ($0$, $1$, or $2$ of them in $S$) the parities match, so this test can't tell those apart. But it's partial information from a single query, and that's new for us.

So we have a new tool: a single query that checks whether all three special positions are in a set. Let's call it the "all-three test". The question is whether this test alone can pin down the positions. And it can, with the same prefix trick as B1:

Three binary searches, $11$ steps each, one query per step: $33$ queries.

all_three(S):                          # single query
    return (query(S) mod 2) != (|S| mod 2)
 
found = {}                             # special positions discovered so far
mx = 2n + 1
repeat 3 times:
    binary search the smallest k in [1, mx] with
        all_three({1..k} ∪ found)
    found.insert(k)
    mx = k - 1
output "!" found                       # the three positions

Accepted for B2 (my submission).