Isaac's Queries

We need answer every interval, but querying every interval is financial suicide: short intervals cost too much. The trick is that the judge array is random, so the prefix XORs behave like random points in a 30-bit cube.

Let

$$p_0=0,\qquad p_i=a_1\oplus a_2\oplus\cdots\oplus a_i.$$

Then

$$f(u,v)=p_v\oplus p_{u-1}.$$

So every required answer is just the highest bit where two prefix XORs differ:

$$ans(u,v)=msb(p_{u-1}\oplus p_v).$$

Now forget the original array. We have $n+1$ hidden 30-bit strings $p_0,p_1,\ldots,p_n$. A query between prefix indices $i<j$ costs $1/(j-i)$ and returns $msb(p_i\oplus p_j)$. We need all pair answers.

Trie View

Put the hidden prefix values into a binary trie, from bit $29$ down to bit $0$.

For two values $x,y$, $msb(x\oplus y)$ is exactly the first trie level where their paths split.

That means:

• if a group of points all share the same high bits, their pair answers are lower;
• if a group splits at bit $b$, then every pair crossing the two children has answer $b$;
• pairs inside one child must be solved recursively.

So if we can recover the trie partition structure, we can fill the whole answer table.

How To Split A Group

Suppose we have a set $S$ of prefix indices that are known to share all bits above the current top differing bit. We want to find their next split.

Pick a pivot $r\in S$. Query $r$ with every other element $x\in S$.

Let

$$mx=\max_{x\in S, x\ne r} msb(p_r\oplus p_x).$$

If no such $x$ exists, the group has size $1$.

Otherwise, $mx$ is the highest bit where this group differs. The pivot is on one side of that split. Every $x$ with query result $mx$ is on the opposite side, because $p_r$ and $p_x$ first differ exactly at this top split bit. Every $x$ with a smaller answer is on the same side as the pivot.

So we split:

• same: pivot plus all $x$ with result $<mx$;
• other: all $x$ with result $=mx$.

Then every cross pair between same and other has answer $mx$. Fill those cells immediately.

Then recurse on both parts.

That is the whole algorithm. Pretty clean, once you stop trying to recover the actual numbers.

Why The Cost Is Okay

A query between prefix indices $i$ and $j$ corresponds to original interval $(\min(i,j)+1,\max(i,j))$, so its cost is

$$\frac{1}{|i-j|}.$$

For each recursive group, we choose the pivot as one of the two extreme indices of the group. Specifically, we try both the minimum and maximum index and take the one with smaller total query cost to the other elements.

That keeps most queried distances large. Since $n=100$, and the hidden values are random, trie splits are usually balanced-ish. The recursion therefore uses only a few hundred cheap long-distance queries per test. Across $30$ tests this fits the robocoin budget.

The Example Is Special

The sample has $n=3$ and is not random. We can just query all missing pairs directly. The total cost is tiny, and it avoids depending on randomness for the sample. For $n=100$, the official tests are random, which is the entire point of this problem.

Correctness Argument

For a query between prefix indices $i$ and $j$, the returned value is $msb(p_i\oplus p_j)$ by definition of prefix XOR. Thus solving all original queries is equivalent to filling this value for all pairs of prefix indices.

Consider any recursive group $S$ where all values share all bits above the current top differing bit. Pick pivot $r\in S$ and query it against every other element of $S$. Let $mx$ be the maximum returned value. No pair in $S$ can differ at a bit above $mx$, otherwise the pivot would differ from at least one side at that bit too. Therefore $mx$ is the highest bit at which the values in $S$ differ.

At bit $mx$, the pivot has one bit value. An element $x$ has the opposite value at bit $mx$ exactly when $msb(p_r\oplus p_x)=mx$. If the answer is smaller, then $x$ matches the pivot at bit $mx$. Therefore the split produced by the algorithm is exactly the trie split of $S$ at bit $mx$.

Every pair crossing the two split parts differs first at bit $mx$, so assigning answer $mx$ to all cross pairs is correct. Pairs inside each part agree at bit $mx$ and all higher bits, so their answers are lower and are handled recursively. The base case of one element has no pairs to fill. By induction over the recursion tree, all pair answers are filled correctly.

Finally, the output for interval $(u,v)$ is the pair answer for prefix indices $(u-1,v)$, so the printed table is correct.