Prime Gaming (Easy Version)

Core idea

The easy version is only scary until you notice $m \le 2$. Then the game is not about arbitrary pile sizes. Each pile is either:

• value $1$, boring baseline
• value $2$, the one extra point Alice wants

So for every configuration, the final value is:

$$x = 1 + [\text{the final pile has value } 2]$$

For $m=2$, there are $2^n$ configurations, so the total answer is:

$$2^n + \#\{\text{configurations where optimal play leaves a }2\}$$

For $m=1$, there is only one configuration and the final value is always $1$, so the answer is just $1$.

That is the whole reduction. Now we only need to count binary configurations where Alice can force the final survivor to be a $2$.

Important detail: good indices are current indices

This is the easiest place to screw up the problem.

The good set is a set of index numbers. After removing a pile, the remaining piles are re-indexed. So if index $2$ is good, that means “the current second pile may be removed,” not “the original pile that started at position $2$ is special.”

Because of that, the game state only depends on the current sequence of pile values, not on original pile identities.

Binary mask state

Encode the current sequence of $p$ piles as a bitmask of length $p$:

• bit $j=0$ means the $(j+1)$-th current pile has value $1$
• bit $j=1$ means the $(j+1)$-th current pile has value $2$

Define two DP tables:

$$A_p[mask] = 1$$

if, from this current sequence of length $p$ with Alice to move, the final pile will be $2$ under optimal play.

$$B_p[mask] = 1$$

if, from this current sequence of length $p$ with Bob to move, the final pile will be $2$ under optimal play.

These are Boolean values, not counts.

Base case

If $p=1$, the game is already over. No one moves. The outcome is just the only remaining pile:

$$A_1[mask] = B_1[mask] = mask$$

Here $mask$ is either $0$ or $1$.

Transition

Suppose there are $p \ge 2$ piles.

A legal move chooses some current index $i$ such that $i$ is marked good and $i \le p$, then removes that pile. In mask terms, removing bit $i-1$ gives a new mask of length $p-1$.

Let $remove(mask, i)$ mean deleting the $i$-th current bit and shifting all later bits left.

Alice chooses the best move for herself. She only needs one move that eventually leaves a $2$:

$$A_p[mask] = \bigvee_{i \in good,\ i \le p} B_{p-1}[remove(mask, i)]$$

Bob chooses the worst move for Alice. The result is still $2$ only if every legal move Bob can make still leaves Alice with a forced $2$:

$$B_p[mask] = \bigwedge_{i \in good,\ i \le p} A_{p-1}[remove(mask, i)]$$

That OR/AND flip is the entire minimax game. No probability, no “expected value,” no funny business.

Counting the answer

After building up to length $n$, the initial position has Alice to move, so we count:

$$wins = \sum_{mask=0}^{2^n-1} A_n[mask]$$

For $m=2$:

$$answer = 2^n + wins$$

The $2^n$ term is the baseline $1$ contributed by every configuration. The $wins$ term adds the extra $1$ for configurations where the final value is $2$.

Why this is enough

The original values are only $1$ or $2$, so knowing which current piles are $2$ fully determines whether Alice prefers a move and whether Bob hates it. Also, legal moves depend only on current indices, and current indices are already represented by the order of bits in the mask. So the mask plus whose turn it is is a complete state.

The induction is straightforward:

• For one pile, the DP is obviously correct.
• For Alice's turn, optimal play means choosing any legal move that makes the final result $2$, hence OR.
• For Bob's turn, optimal play means choosing a legal move that makes the final result $1$ if possible, hence the result is $2$ only if all options are $2$, hence AND.

So the DP computes exactly the optimal-play outcome for every binary configuration.

Complexity

For each length $p$, there are $2^p$ masks, and we try up to $k \le n$ good indices.

Total complexity per test case:

$$O\left(\sum_{p=1}^{n} k \cdot 2^p\right) = O(n2^n)$$

up to a small constant. With $n \le 20$ and the global $\sum 2^n$ bound, this is completely fine.