Editorial: Prime Gaming (Easy Version)

The key is to solve the game in layers:

1. one fixed configuration,
2. one threshold query on that configuration,
3. then sum over all configurations.

Suppose the pile values are fixed. The game only removes indices, so the final pile value is the value of the surviving original position.

Directly optimizing numeric values is awkward, so for a chosen threshold $a$, convert values to bits:

• bit $0$: value $< a$
• bit $1$: value $\ge a$

Now the question becomes:

Can Alice force the final bit to be $1$?

If yes, then for this configuration we have $x \ge a$.

For current length $l$, a state is a length-$l$ bitmask mask (bit $j$ is the current $j$-th pile’s label after thresholding). Legal moves are indices $i$ such that $i$ is marked good in the current indexing; removing $i$ deletes bit $i$ from mask.

Define:

where $1$ means “Alice can force final bit $1$ from this state”.

Turn is determined only by remaining length:

• total moves in game: $n - 1$
• moves already played at length $l$: $n - l$

So:

• if $(n - l)$ is even, it is Alice’s turn,
• otherwise it is Bob’s turn.

For $l = 1$, no move remains, so:

Suppose we are at length $l$ and remove position $i$ ($0 \le i < l$). Let:

• high = mask >> (i + 1) (bits strictly above $i$),
• low = mask & ((1 << i) - 1) (bits below $i$).

Then next mask (length $l - 1$) is:

This is exactly “drop bit $i$ and compact”.

Now minimax:

• Alice turn:
  $$ \text{dp}[l][\text{mask}] = \bigvee_{\text{legal } i} \text{dp}[l-1][\text{next}(i)]. $$
• Bob turn:
  $$ \text{dp}[l][\text{mask}] = \bigwedge_{\text{legal } i} \text{dp}[l-1][\text{next}(i)]. $$

Equivalent implementation style:

• initialize value to $0$ on Alice turn and set to $1$ if any legal move gives $1$,
• initialize value to $1$ on Bob turn and set to $0$ if any legal move gives $0$.

If $l = 4$, mask = 1101₂, and we remove $i = 1$:

• high = 11₂, low = 1₂,
• next = (11₂ << 1) | 1₂ = 111₂.

So state 1101 at length $4$ goes to state 111 at length $3$ via that move.

Because $n \le 20$ and $\sum 2^n$ is limited, this DP over all masks is feasible.

Let $K_c$ be:

number of winning masks (for the full length $n$) having exactly $c$ positions with value $< a$.

For such a mask:

• each of those $c$ positions has $(a - 1)$ choices,
• each of the other $n-c$ positions has $(m - a + 1)$ choices.

So arrays contributing to that mask:

Hence

Use the standard threshold identity:

Reason: each array with final value $x$ is counted once in every $F(a)$ for $a \le x$.

For E1, $m \le 2$, so this outer sum is tiny.

A common idea is: for each value $v$, mark positions with value exactly $v$ and run the same binary DP. This does not match the real minimax objective.

Counterexample:

• $n = 3$
• good indices are $1,2$
• values are $[1,1,2]$

In the real game, Alice first removes one of the two $1$’s, leaving $[1,2]$. Then Bob (minimizer) removes $2$, so final value is $1$. Hence the true answer is $1$.

Now try the equality mask for value $1$: bits are $[1,1,0]$. After Alice’s first move, state is $[1,0]$. In this mask-game, Bob wants final bit $0$, so he removes the bit-$1$ pile and leaves bit $0$. Therefore “can force value exactly $1$” becomes false, contradicting the true game answer.

The issue: equality masks treat values $> v$ as “bad”, while in the original game they are at least as good as $v$ for Alice. Threshold masks ($\ge v$) preserve the correct order of preferences.

• DP over masks and lengths: $O(n^2 2^n)$ in a straightforward implementation
• Threshold loop: $O(mn)$

This is easily fast enough for E1 constraints.