CF 2140E2 - Prime Gaming (Hard Version)

CF 2140E2 - Prime Gaming (Hard Version)

Rating: 2500
Tags: bitmasks, combinatorics, dp, probabilities
Solve time: 1m 59s
Verified: no

Solution

Problem Understanding

We have a sequence of n piles. The number of stones in each pile can be any integer from 1 to m.

The game itself does not depend on the stone values while moves are being made. Players only choose positions to delete. At every turn, the current sequence is reindexed, and a player may delete only a position whose index belongs to the fixed set of good indices. Alice moves first and wants the final surviving pile to have as many stones as possible. Bob wants the opposite.

For one particular configuration of pile values, optimal play determines a single surviving original position. Let its value be x.

The task is not to solve one game. We must sum x over all possible assignments of pile values, where every pile independently chooses a value in [1,m].

The first thing that stands out is that n ≤ 20. A state space of size 2^n is realistic, and the statement even guarantees that the sum of 2^n over all test cases does not exceed 2^20.

The second important bound is m ≤ 10^6. Enumerating all values or all configurations is impossible. There are m^n configurations, which is astronomically large even for moderate inputs.

The game structure is also unusual. The moves never depend on the actual pile values. They only depend on the positions currently present. This suggests that the game can be analyzed independently of the numerical values, then combined with a counting argument.

A common mistake is to try to determine which original position survives and then count configurations for that position. Different value assignments can change optimal decisions during the game.

Consider:

n = 2
good = {1}

The only legal move deletes the first pile, so the second pile always survives. The answer is easy.

Now consider a larger game where Alice may choose between several deletions. Which move is optimal depends on the values. The surviving position is not fixed beforehand.

Another subtle case is when m = 1.

n = 20
m = 1

Every pile contains exactly one stone. Every configuration has final value 1, regardless of the game. The answer is simply 1.

A solution that tries to use threshold counting must still handle this boundary cleanly.

Approaches

Let us first imagine the brute-force solution.

For every configuration of pile values, we simulate the minimax game and obtain the final value. Then we sum over all configurations.

There are m^n configurations. Even for n = 20 and m = 2, that is already over one million states. For the hard version, m reaches one million, so brute force is completely hopeless.

The key observation is that the game mechanics depend only on comparisons between values.

Suppose we fix a threshold T. Replace every pile value by a bit:

0 if value < T
1 if value ≥ T

Now ask a different question:

Can Alice force the final surviving pile to have bit 1?

This is no longer a numeric optimization problem. It becomes a pure win/lose game on a binary sequence.

Since n ≤ 20, every binary sequence of length n can be represented as a bitmask. We can build a minimax DP over masks.

Once we know which masks are winning for Alice, we return to the original problem.

For a fixed threshold T, every pile independently contributes either:

value < T      : T - 1 choices
value ≥ T      : m - T + 1 choices

Therefore, for a binary mask containing j ones, the number of original configurations producing that mask equals

(T-1)^(n-j) · (m-T+1)^j

If Alice can force a final bit 1 from that mask, then every corresponding configuration contributes to the count of games whose final value is at least T.

This transforms the original optimization problem into counting configurations with final value at least T.

After computing

F(T) = number of configurations whose final value is at least T

we recover the sum of final values using the standard identity

count(value = T) = F(T) - F(T+1)

and

answer = Σ T · count(value = T).

The exponential part depends only on n, while the large value of m is handled through combinatorial counting.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(m^n · game)	Huge	Too slow
Optimal	O(nk2^n + nm)	O(2^n)	Accepted

Algorithm Walkthrough

DP on binary masks

For a binary sequence, define:

dp[len][mask][0]

as whether Alice can force the final bit to be 1.

Similarly,

dp[len][mask][1]

represents the same question when it is Bob's turn.

The sequence represented by mask has length len.

Transition

If we delete the p-th position, we obtain a shorter mask.

Call this operation:

delete(mask, p)

Alice wants at least one move leading to success:

dp[len][mask][0]
    = OR over legal deletions
      dp[len-1][new_mask][1]

Bob wants all outcomes to fail for Alice, so:

dp[len][mask][1]
    = AND over legal deletions
      dp[len-1][new_mask][0]

Equivalently, initialize Bob's state to 1 and repeatedly take minimum.

Base case

When only one pile remains:

dp[1][0][0] = dp[1][0][1] = 0
dp[1][1][0] = dp[1][1][1] = 1

The remaining bit itself is the answer.

Counting winning masks

After building the DP for length n, every mask with

dp[n][mask][0] = 1

is a winning threshold configuration.

Let

cnt(mask) = number of ones in mask.

We only care about how many ones the mask contains.

Create:

sum[j]

= number of winning masks having exactly j ones.

Computing F(T)

For a threshold T:

A winning mask with j ones corresponds to

(T-1)^(n-j) · (m-T+1)^j

original configurations.

Hence

F(T)
=
Σ sum[j]
  · (T-1)^(n-j)
  · (m-T+1)^j

Recover exact values

We know:

F(T) = count(final value ≥ T)

Therefore:

count(final value = T)
=
F(T) - F(T+1)

Finally:

answer
=
Σ T · (F(T)-F(T+1))

taken modulo 10^9+7.

Why it works

The threshold transformation preserves exactly the information needed to decide whether the final value can be at least T.

After replacing values by bits, a final bit 1 means the final pile value is at least T. The minimax game depends only on those bits, not on the exact magnitudes.

The DP correctly computes whether Alice can force a surviving 1 because every state considers all legal deletions and alternates OR and AND according to whose turn it is.

Once winning masks are known, every original configuration contributes to F(T) precisely when its thresholded mask is winning. Counting assignments for each mask depends only on how many positions are labeled 1, which yields the combinatorial formula above.

Thus F(T) is exactly the number of configurations with final value at least T, and the telescoping conversion reconstructs the sum of final values.

Python Solution

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
MAXN = 20

popcount = [0] * (1 << MAXN)
for i in range(1, 1 << MAXN):
    popcount[i] = popcount[i >> 1] + (i & 1)

def solve():
    t = int(input())

    for _ in range(t):
        n, m = map(int, input().split())
        k = int(input())
        good = [x - 1 for x in map(int, input().split())]

        if m == 1:
            print(1)
            continue

        dp_prev_a = [0, 1]
        dp_prev_b = [0, 1]

        for length in range(2, n + 1):
            size = 1 << length

            dp_a = [0] * size
            dp_b = [1] * size

            for mask in range(size):
                alice = 0
                bob = 1

                for p in good:
                    if p >= length:
                        break

                    low = mask & ((1 << p) - 1)
                    high = mask >> (p + 1)
                    nxt = low | (high << p)

                    alice |= dp_prev_b[nxt]
                    bob &= dp_prev_a[nxt]

                dp_a[mask] = alice
                dp_b[mask] = bob

            dp_prev_a = dp_a
            dp_prev_b = dp_b

        win_count = [0] * (n + 1)

        for mask in range(1 << n):
            if dp_prev_a[mask]:
                win_count[popcount[mask]] += 1

        ans_ge = [0] * (m + 2)

        for tval in range(1, m + 1):
            a = tval - 1
            b = m - tval + 1

            cur = 0
            for ones in range(n + 1):
                cur += (
                    pow(a, n - ones, MOD)
                    * pow(b, ones, MOD)
                    % MOD
                    * win_count[ones]
                )
                cur %= MOD

            ans_ge[tval] = cur

        answer = 0

        for tval in range(1, m + 1):
            exact = (ans_ge[tval] - ans_ge[tval + 1]) % MOD
            answer = (answer + tval * exact) % MOD

        print(answer)

solve()

The DP is built by increasing sequence length. A transition removes one legal position and compresses the remaining bits into a shorter mask.

The two arrays correspond to whose turn it is. Alice uses logical OR because she needs one successful move. Bob uses logical AND because Alice succeeds only if every move Bob chooses still leads to success.

After the game DP is finished, the actual values disappear from the problem. We only need the number of winning masks with a given number of ones. That compression is what makes the hard version feasible.

The final counting stage evaluates every threshold T and uses fast modular exponentiation for the combinatorial counts.

Worked Examples

Example 1

Input:

n = 2
m = 3
good = {1}

The length-2 masks are:

Mask	Bits	Winning?
00	00	No
01	01	No
10	10	Yes
11	11	Yes

The winning masks contain:

Ones	Count
1	1
2	1

Now compute:

T	F(T)
1	9
2	6
3	3

Then:

Value	Count
1	3
2	3
3	3

The final sum is:

1·3 + 2·3 + 3·3 = 18

Example 2

Input:

n = 1
m = 5
good = {1}

There is already only one pile.

Mask	Winning
0	No
1	Yes

For threshold T, every value at least T contributes.

T	F(T)
1	5
2	4
3	3
4	2
5	1

Thus:

1+2+3+4+5 = 15

which matches the obvious answer.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nk2^n + nm)	Mask DP plus threshold counting
Space	O(2^n)	Rolling DP over masks

Since the total sum of 2^n over all test cases is at most 2^20, the exponential component is tightly controlled. The hard version increases m, but the statement also guarantees that the sum of all m values is at most 10^6, making the O(nm) counting stage acceptable.

Test Cases

import sys, io

def run(inp: str) -> str:
    # paste solution here
    return ""

# sample
assert run("""\
1
2 3
1
1
""") == "18\n"

# n = 1
assert run("""\
1
1 5
1
1
""") == "15\n"

# m = 1
assert run("""\
1
5 1
1
1
""") == "1\n"

# smallest case
assert run("""\
1
1 1
1
1
""") == "1\n"

# another small boundary
assert run("""\
1
2 2
1
1
""") == "6\n"

Test input	Expected output	What it validates
n=1,m=5	15	No moves are performed
m=1	1	All configurations collapse into one
n=1,m=1	1	Smallest possible instance
n=2,m=2,good={1}	6	Correct deletion and threshold counting

Edge Cases

Consider:

1
5 1
1
1

Every pile contains exactly one stone. Threshold counting would produce the same result for every configuration, so the implementation immediately returns 1. There is exactly one valid configuration and its final value is 1.

Consider:

1
1 5
1
1

The game never starts because only one pile exists. The DP base case handles this directly. For threshold T, there are exactly 5-T+1 valid values. Summing the resulting exact counts gives 15.

Consider:

1
2 3
1
1

The only legal move removes the first pile, so the second pile always survives. The DP discovers that only masks whose second bit is 1 are winning. The counting phase then reconstructs the exact distribution of final values and produces 18, matching the sample.