Editorial: Prime Gaming (Easy Version)
The key is to solve the game in layers:
- one fixed configuration,
- one threshold query on that configuration,
- 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 the current length-$l$ bit sequence. Moves: remove any currently good index $i$ (indices are re-numbered after each deletion).
Let win(state) be whether Alice can force final bit $1$ from this state under optimal play.
- Base ($l = 1$):
winequals the only bit. - Transition:
- Alice’s turn: OR over legal next states.
- Bob’s turn: AND over legal next states.
Because $n \le 20$ and $\sum 2^n$ is limited, 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:
$$ (a - 1)^c (m - a + 1)^{n-c}. $$Hence
$$ F(a) = \#\{\text{arrays with final } x \ge a\} = \sum_{c=0}^{n} K_c (a - 1)^c (m - a + 1)^{n-c}. $$Use the standard threshold identity:
$$ \sum_{\text{arrays}} x = \sum_{a=1}^{m} F(a). $$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.
- 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.