Editorial : Interval Game

Editorial (model solution)

The following editorial describes the model approach implemented in model_sol.cpp.

Represent an interval on $[1, x]$ by $a = l - 1$ and $b = x - r$. After reading $x_1$ and $x_2$, the program stores $X_1 = x_1 - 1$ and $X_2 = x_2 - 1$ so that feasible pairs satisfy $a + b \le X_1$ and $a_2 + b_2 \le X_2$.

Alice chooses $t = a_1 \oplus b_1$; Bob’s random interval contributes $u = a_2 \oplus b_2$. She loses exactly when $u = t$. For each candidate XOR value $c$, let $F(c)$ be the number of valid second-interval pairs $(a_2, b_2)$ with $a_2 \oplus b_2 = c$ and $a_2 + b_2 \le X_2$. Alice should pick $t \in [0, X_1]$ minimizing $F(t)$.

To compute all $F(c)$, note that for a fixed $a = i$, the admissible $b$ are $0 \le b \le X_2 - i$. For each $i$, decompose that range of $b$ into $O(\log X_2)$ power-of-two blocks. On a block starting at minj with length $2^b$, XOR values $i \oplus b$ for $b$ in that block have a fixed prefix on the lower bits; the code applies a difference-map update at f and f + (1 << b) for the appropriate f. A sweep over $c = 0, \dots, X_1$ with prefix sums recovers $F(c)$ and picks the minimizing $c$ (smallest on ties).

Output the interval with $(a_1, b_1) = (0, t)$: in original coordinates $l_1 = 1$ and $r_1 = x_1 - t$, which matches 1 and X1 + 1 - best after the decrements.

Let an interval $[l, r]$ inside $[1, x]$ be represented by:

$$ a=l-1,\qquad b=x-r. $$

In one move, we can decrease $l$ (so decrease $a$ to any smaller nonnegative value) or increase $r$ (so decrease $b$ to any smaller nonnegative value).
Hence $a$ and $b$ are two independent Nim heaps, and this interval has Grundy value:

$$ g=a\oplus b. $$

For the whole game, with intervals $[l_1,r_1]$ and $[l_2,r_2]$, the total Grundy value is:

$$ (a_1\oplus b_1)\oplus(a_2\oplus b_2). $$

Alice fixes the first interval, so she fixes:

$$ t=a_1\oplus b_1. $$

The second interval is random; define:

$$ u=a_2\oplus b_2. $$

Alice loses exactly when total Grundy is $0$, i.e. when $u=t$.

So for fixed $t$, loss count is:

$$ f(t)=\#\{(a_2,b_2)\mid a_2,b_2\ge0,\ a_2+b_2\le n,\ a_2\oplus b_2=t\}, $$

where $n=x_2-1$. Minimizing $f(t)$ maximizes winning probability.

For fixed $t$, let:

$$ u=a_2\&b_2. $$

Then:

$$ a_2+b_2=(a_2\oplus b_2)+2(a_2\&b_2)=t+2u. $$

So we need:

$$ u\le \left\lfloor\frac{n-t}{2}\right\rfloor,\qquad u\&t=0. $$

For each valid $u$, every $1$-bit of $t$ can be assigned independently to either $a_2$ or $b_2$, giving:

$$ 2^{\operatorname{popcount}(t)} $$

pairs $(a_2,b_2)$.

Therefore (for $t\le n$):

$$ f(t)=2^{\operatorname{popcount}(t)} \cdot \#\left\{u\ \middle|\ 0\le u\le \left\lfloor\frac{n-t}{2}\right\rfloor,\ u\&t=0\right\}, $$

and for $t>n$, $f(t)=0$.

The remaining count is a standard binary digit-DP with a tight flag: count numbers $u\le M$ such that forbidden bits (where $t$ has $1$) are never set.

Now we only need to decide which $t$ Alice can realize.

Let $m=x_1-1$.
Any $t\in[0,m]$ is realizable: choose $(a_1,b_1)=(t,0)$, i.e.

$$ l_1=t+1,\qquad r_1=x_1, $$

which is valid since $a_1+b_1=t\le m$.

So we scan all $t=0..m$, compute $f(t)$, and pick one with minimum value.

If multiple are optimal, any is accepted.

Complexity

For one test case:

iterate $t=0..x_1-1$,
each $t$ uses $O(\log x_2)$ bit-DP.

Total:

$$ O(x_1\log x_2) $$

time and $O(1)$ extra memory.