Interval Game

Observation 1

This game is just Nim wearing an interval costume.

For one interval $[l,r]$ inside $[1,x]$, define the two gaps $a=l-1, \qquad b=x-r.$ A move decreases exactly one of $a$ or $b$ to any smaller nonnegative integer. That is literally a 2-heap Nim position, so its Grundy value is $g(a,b)=a\oplus b.$

For two intervals, the whole game is the disjoint sum of two such positions, hence the total Grundy value is

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

Alice loses iff this xor is $0$, i.e. iff

$$a_1\oplus b_1=a_2\oplus b_2.$$

So Alice only cares about choosing the Grundy value of her own interval. That is the first big aha. Everything else is decorative bullshit.

Observation 2

Let $n_1=x_1-1$. Any value $k\in[0,n_1]$ is achievable: just take

$$a_1=k,\qquad b_1=0,$$

which corresponds to the interval

$$[l_1,r_1]=[k+1,x_1].$$

Therefore Alice should pick some $k\in[0,x_1-1]$ minimizing the number of random intervals in $[1,x_2]$ whose Grundy value is also $k$.

If $x_1>x_2$, then she can even choose $k=x_2$. But for the second interval we always have

$$a_2+b_2\le x_2-1 \implies a_2\oplus b_2\le x_2-1,$$

so that $k$ can never appear. Then Alice wins with probability $1$. Free candy.

Counting intervals with xor $k$

For the random interval, set

$$a=l_2-1,\qquad b=x_2-r_2,\qquad n=x_2-1.$$

Every valid interval corresponds bijectively to one pair $(a,b)$ with $a,b\ge 0$ and $a+b\le n$.

We need

$$f_n(k)=\#\{(a,b): a+b\le n,\ a\oplus b=k\}.$$

Now introduce

$$t=a\mathbin{\&}b.$$

Using the identity

$$a+b=(a\oplus b)+2(a\mathbin{\&}b),$$

we get

$$a+b=k+2t.$$

Also, any bit set in $k$ cannot be set in $t$, so

$$t\mathbin{\&}k=0.$$

Conversely, fix any $t$ with $t\mathbin{\&}k=0$. For every bit where $k$ has a $1$, that bit must belong to exactly one of $a,b$, giving $2$ choices independently per set bit. Therefore each valid $t$ creates exactly

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

ordered pairs $(a,b)$.

So we get the clean formula

$$f_n(k)= \begin{cases} 2^{\operatorname{popcount}(k)}\cdot \#\left\{t:0\le t\le \left\lfloor\dfrac{n-k}{2}\right\rfloor,\ t\mathbin{\&}k=0\right\}, & k\le n,\\[1ex] 0, & k>n. \end{cases}$$

That is the whole counting problem. No black magic, just bits.

Bit DP for the remaining count

So we only need

$$C(m,k)=\#\{t:0\le t\le m,\ t\mathbin{\&}k=0\}.$$

This is a standard binary digit DP with two states:

• equal: the processed prefix of $t$ is exactly equal to the processed prefix of $m$;
• less: the processed prefix is already smaller.

At bit $b$:

• if bit $b$ of $k$ is $1$, then bit $b$ of $t$ must be $0$;
• otherwise, bit $b$ of $t$ can be $0$ or $1$, as long as we do not exceed $m$.

That gives an $O(\log x_2)$ routine for $C(m,k)$, hence also for $f_n(k)$.

Final algorithm

For each test case:

1. If $x_1>x_2$, output any interval with Grundy $x_2$, for example $[x_2+1,x_1]$.
2. Otherwise, for every $k=0,1,\dots,x_1-1$:
   • compute $f_{x_2-1}(k)$ with the formula above and the bit DP,
   • keep the $k$ with minimum value.
3. Output $[k+1,x_1]$.

The total number of possible second intervals is

$$\frac{x_2(x_2+1)}{2},$$

so the winning probability for Alice is

$$1-\frac{f_{x_2-1}(k)}{x_2(x_2+1)/2}.$$

The denominator does not depend on her choice, so minimizing $f_{x_2-1}(k)$ is exactly what we want.

Complexity

Let $X=5\cdot 10^5$. For each candidate $k$ we do one $O(\log X)$ bit DP, and we scan all $k=0..x_1-1$.

So the complexity per test case is

$$O(x_1\log X),$$

and over all test cases it is

$$O\left(\left(\sum x_1\right)\log X\right),$$

which is easily fast enough since $\sum x_1\le 5\cdot 10^5$. Memory usage is $O(1)$.