Prime Gaming (Hard Version)

Let the pile values be $a_1,\dots,a_n$. The deletion rules depend only on positions, but the players' goals depend on the final value. Directly simulating minimax over all values is dead on arrival: $m^n$ configurations, welcome to pain.

The clean way out is to turn values into thresholds.

For any final value $x$,

$$x = \sum_{y=1}^{m} [x \ge y].$$

So instead of summing final values directly, we can sum, for every threshold $y$, how many configurations let Alice force the final pile to have value at least $y$.

For a fixed $y$, each pile becomes binary:

• high if $a_i \ge y$,
• low if $a_i < y$.

Alice wants the final pile to be high. Bob wants the final pile to be low. Now the actual values are irrelevant. The whole game is just: given a subset $S$ of original pile indices marked high, can Alice force the final remaining pile to belong to $S$?

Game DP on Remaining Piles

Represent the remaining original piles by a bitmask $mask$. Their current order is the natural order of original indices still present.

A move may remove the pile whose current rank is in the good-index set. Example: if remaining original piles are $[2,5,9]$, then original pile $5$ currently has rank $2$.

Let $can[S]$ mean: starting from all piles present, with high piles exactly $S$, Alice can force the final pile to be high.

To compute this, define a recursive minimax state $f(mask)$ for this fixed $S$:

• if only one pile remains, $f(mask)=1$ iff that remaining pile is in $S$;
• otherwise, determine whose turn it is from the number of removed piles:
  • Alice moves when $n-|mask|$ is even;
  • Bob moves when $n-|mask|$ is odd.

From state $mask$, the legal moves are exactly the remaining piles whose current rank is marked good.

If it is Alice's turn, she wants success, so

$$f(mask)=\bigvee_{move} f(mask\setminus\{move\}).$$

If it is Bob's turn, he wants Alice to fail, so Alice succeeds only if Bob has no escape:

$$f(mask)=\bigwedge_{move} f(mask\setminus\{move\}).$$

The answer for high set $S$ is $f((1<<n)-1)$.

Now doing this separately for all $S$ with a fresh recursive DP would be too much. But $n\le 20$ and the total $2^n$ over tests is bounded, so we can compute the result for all $S$ at once using bitsets.

Bitset DP Over All High Sets

For every remaining-piles mask $mask$, store a bitset $dp[mask]$ over all possible high masks $S$:

$$dp[mask][S] = 1$$

means Alice can force a high final pile from state $mask$ when the high set is $S$.

Base case: if $mask$ has one remaining pile $i$, then Alice wins exactly when $i\in S$. Therefore $dp[mask]$ is the bitset of all $S$ containing bit $i$.

Transition:

• Alice turn: OR the child bitsets.
• Bob turn: AND the child bitsets.

This is nice because the same game graph works for every $S$. We only combine whole bitsets.

There are at most $2^n$ states, and each bitset has $2^n$ bits, so the rough cost is $O(4^n / 64)$ bit operations. For $n=20$, this is fine in C++ if implemented sanely. Big, but not stupid-big.

Counting Configurations

After the DP, $dp[full][S]=1$ tells us exactly which high masks are winning for Alice.

For a fixed threshold $y$, if the high mask is $S$:

• each high pile has $m-y+1$ possible values;
• each low pile has $y-1$ possible values.

So the number of configurations producing this $S$ is

$$(m-y+1)^{|S|}(y-1)^{n-|S|}.$$

Only $|S|$ matters for this count. Let

$$cnt[j] = \#\{S : dp[full][S]=1 \text{ and } |S|=j\}.$$

Then the answer is

$$\sum_{y=1}^{m}\sum_{j=0}^{n} cnt[j](m-y+1)^j(y-1)^{n-j}.$$

Reindex $b=y-1$, so $b$ goes from $0$ to $m-1$ and $m-y+1=m-b$:

$$ans = \sum_{b=0}^{m-1}\sum_{j=0}^{n} cnt[j](m-b)^j b^{n-j}.$$

Since $n\le20$ and the total $m$ is at most $10^6$, evaluating this directly over all $b$ and all $j$ is completely fine.

Why This Actually Matches the Original Game

The only subtle point is thresholding. Minimax with numeric values can look scary because Alice and Bob compare actual pile values, not just high/low labels.

But the identity

$$x = \sum_{y=1}^{m} [x\ge y]$$

lets us decompose the numeric payoff into independent Boolean games. For each threshold $y$, Alice maximizing $x$ is equivalent to Alice trying to make $[x\ge y]=1$, and Bob minimizing $x$ is equivalent to Bob trying to make it $0$. Deterministic finite zero-sum games with perfect information behave perfectly under this threshold view: for each $y$, either Alice can force a final pile at least $y$, or Bob can prevent it.

Then we count all assignments that make that Boolean win happen. No probability hand-waving, no bogus linearity assumption. Just threshold sums doing the heavy lifting.