CF 2140E1 - Prime Gaming (Easy Version)
We have a row of n piles. Each pile contains either 1 or 2 stones because this is the easy version and m ≤ 2. The game does not modify pile values. Players only remove piles.
CF 2140E1 - Prime Gaming (Easy Version)
Rating: 2200
Tags: bitmasks, combinatorics, dp
Solve time: 1m 59s
Verified: yes
Solution
Problem Understanding
We have a row of n piles. Each pile contains either 1 or 2 stones because this is the easy version and m ≤ 2.
The game does not modify pile values. Players only remove piles. At any moment, the current piles are re-indexed from left to right, and a move consists of deleting a pile whose current index belongs to the fixed set of good indices.
Alice moves first and wants the value of the final surviving pile to be as large as possible. Bob wants it as small as possible.
For every possible assignment of pile values, we play the game optimally and obtain the value of the last remaining pile. The task is to sum that value over all configurations.
The first thing worth noticing is that the game mechanics depend only on positions, never on the actual numbers written in the piles. The values only matter when we evaluate the final surviving position.
The constraint n ≤ 20 is the key. A state of the game can be represented by the set of surviving positions, and 2^20 is roughly one million. The statement even guarantees that the total sum of 2^n over all test cases is at most 2^20, which strongly suggests a bitmask dynamic programming solution.
A common mistake is to try to compute directly which original position survives. That position depends on optimal play and changes after every re-indexing. The game is a minimax game over dynamically changing sequences, not a simple elimination process.
Consider the input
3 2
2
1 2
If the piles are [2,1,2], Alice can remove the second pile, leaving [2,2]. Bob must then remove the first pile, and the final value is 2. Any approach that tries to assign a fixed "surviving position" to the game state misses this interaction.
Another subtle case is when n = 1.
1 2
1
1
No moves are played at all. The only pile survives immediately. Any DP that assumes at least one deletion would produce the wrong result.
Approaches
The most direct brute force is to enumerate all m^n configurations. For each configuration we could run a minimax search over the game tree and determine the final value.
For n = 20, even the number of configurations is already 2^20 ≈ 10^6, and each configuration would require solving a game. This is far too expensive.
The crucial observation is that the game only compares pile values. Since m ≤ 2, every pile is either 1 or 2.
Suppose we encode a configuration as a binary sequence:
1 stone -> 0
2 stones -> 1
Now the final answer for that configuration is either 0 or 1 in this binary world. We only need to know whether Alice can force the final surviving pile to be a 1.
This transforms the problem into a pure game on binary sequences.
A state is simply the current binary sequence. When a pile is removed, one bit disappears. Since n ≤ 20, every sequence of length ℓ can be represented by a bitmask of ℓ bits.
The minimax value of a state is also binary:
0 = Bob can force the final bit to be 0
1 = Alice can force the final bit to be 1
This leads to a DP over all masks of all lengths.
After we know which length-n masks evaluate to 1, counting configurations becomes easy. Every binary mask corresponds to exactly one configuration because values are only 1 and 2.
The final pile value equals:
1 + (game result bit)
So
sum(final values)
=
(number of configurations)
+
(number of masks whose game result is 1)
For m = 2, the number of configurations is 2^n.
For m = 1, every configuration consists entirely of ones, so the answer is simply 1.
The DP processes all masks exactly once and uses the guarantee that the total sum of 2^n is bounded. This yields an accepted solution.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | Exponential in both configurations and game states | Exponential | Too slow |
| Optimal Bitmask DP | O(n · 2^n) | O(2^n) | Accepted |
Algorithm Walkthrough
Step 1
Handle the special case m = 1.
Every pile contains exactly one stone, so every configuration is identical and the final answer is always 1.
Step 2
For m = 2, represent each configuration as a binary mask.
Bit i = 0 means the pile contains 1.
Bit i = 1 means the pile contains 2.
Step 3
Define a DP value for every sequence mask.
dp[mask] represents whether Alice can force the final surviving bit to be 1 from that state.
The length of the sequence is determined by the number of bits currently stored in the mask layer.
Step 4
Initialize length 1.
If the only remaining bit is 0, the result is 0.
If the only remaining bit is 1, the result is 1.
Step 5
Process lengths from 2 up to n.
For a mask of length ℓ, determine whose turn it is.
Exactly n - ℓ deletions have already happened.
If n - ℓ is even, it is Alice's turn.
If n - ℓ is odd, it is Bob's turn.
Step 6
Generate every legal child state.
For every good index c with c ≤ ℓ, delete the c-th bit from the current mask.
This produces a mask of length ℓ - 1.
Step 7
Apply minimax.
If it is Alice's turn, the state value is the OR of all child values.
Alice only needs one move leading to a winning child.
If it is Bob's turn, the state value is the AND of all child values.
Bob chooses the move that is worst for Alice.
Step 8
After computing all masks of length n, count how many have DP value 1.
Let this count be win.
The answer is
2^n + win
taken modulo 10^9 + 7.
Why it works
The DP value of a state is exactly the minimax value of that game position.
The base case is correct because when only one pile remains, the final bit is already known.
For any larger state, every legal move produces a smaller state. If Alice moves, she chooses the child maximizing the result, which is precisely an OR over binary outcomes. If Bob moves, he chooses the child minimizing the result, which is precisely an AND over binary outcomes.
By induction on sequence length, every DP value equals the true game-theoretic value of that state.
A length-n mask evaluates to 1 exactly when the corresponding configuration ends with value 2 under optimal play. Adding the number of such masks to the baseline contribution of 1 from every configuration gives the required sum.
Python Solution
import sys
input = sys.stdin.readline
MOD = 1000000007
def solve():
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
k = int(input())
good = list(map(int, input().split()))
if m == 1:
print(1)
continue
dp = [None] * (n + 1)
dp[1] = [0, 1]
for length in range(2, n + 1):
size = 1 << length
cur = [0] * size
alice_turn = ((n - length) & 1) == 0
valid_good = [x for x in good if x <= length]
for mask in range(size):
if alice_turn:
val = 0
for pos in valid_good:
idx = pos - 1
low = mask & ((1 << idx) - 1)
high = mask >> (idx + 1)
child = low | (high << idx)
val |= dp[length - 1][child]
if val:
break
cur[mask] = val
else:
val = 1
for pos in valid_good:
idx = pos - 1
low = mask & ((1 << idx) - 1)
high = mask >> (idx + 1)
child = low | (high << idx)
val &= dp[length - 1][child]
if not val:
break
cur[mask] = val
dp[length] = cur
win = sum(dp[n])
ans = ((1 << n) + win) % MOD
print(ans)
solve()
The DP is organized by sequence length. dp[length][mask] stores the minimax result for that exact sequence.
The expression used to delete a bit is the most delicate part of the implementation. We split the mask into bits before the deleted position and bits after it. The upper part is shifted right by one position and merged back.
Another detail is turn detection. A state of length length appears after exactly n - length deletions. Since Alice moves first, parity of this number uniquely determines whose turn it is.
The memory usage stays small because the total number of stored states is
2 + 4 + 8 + ... + 2^n
=
2^(n+1) - 2
which is below two million when n = 20.
Worked Examples
Example 1
Input
2 2
1
1
Only index 1 is good.
There are four masks of length 2.
| Mask | Sequence | Child after deleting first pile | Result |
|---|---|---|---|
| 00 | [1,1] | 0 | 0 |
| 01 | [2,1] | 0 | 0 |
| 10 | [1,2] | 1 | 1 |
| 11 | [2,2] | 1 | 1 |
win = 2.
Total answer:
2^2 + 2 = 6
This example shows that the DP value really represents whether the final pile is a 2.
Example 2
Input
3 2
2
1 2
Length 1 values:
| Mask | DP |
|---|---|
| 0 | 0 |
| 1 | 1 |
Length 2 states belong to Bob.
| Mask | Children | DP |
|---|---|---|
| 00 | 0,0 | 0 |
| 01 | 1,0 | 0 |
| 10 | 0,1 | 0 |
| 11 | 1,1 | 1 |
Length 3 states belong to Alice.
| Mask | Children | DP |
|---|---|---|
| 000 | 00,00 | 0 |
| 001 | 01,00 | 0 |
| 010 | 00,10 | 0 |
| 011 | 01,10 | 0 |
| 100 | 10,01 | 0 |
| 101 | 11,01 | 1 |
| 110 | 10,11 | 1 |
| 111 | 11,11 | 1 |
win = 3.
Answer:
8 + 3 = 11
This matches the sample output.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n · 2^n) | Every mask is processed once, each with at most n legal deletions |
| Space | O(2^n) | The total DP storage is proportional to the number of masks |
The largest test has n = 20, so 2^n is roughly one million. The statement guarantees that the sum of 2^n across all test cases does not exceed 2^20, making this complexity comfortably fast enough.
Test Cases
# helper: run solution on input string, return output string
import sys, io
def run(inp: str) -> str:
input_data = io.StringIO(inp)
out = io.StringIO()
MOD = 1000000007
def input():
return input_data.readline()
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
k = int(input())
good = list(map(int, input().split()))
if m == 1:
out.write("1\n")
continue
dp = [None] * (n + 1)
dp[1] = [0, 1]
for length in range(2, n + 1):
cur = [0] * (1 << length)
alice_turn = ((n - length) & 1) == 0
valid_good = [x for x in good if x <= length]
for mask in range(1 << length):
if alice_turn:
val = 0
for pos in valid_good:
idx = pos - 1
low = mask & ((1 << idx) - 1)
high = mask >> (idx + 1)
child = low | (high << idx)
val |= dp[length - 1][child]
if val:
break
cur[mask] = val
else:
val = 1
for pos in valid_good:
idx = pos - 1
low = mask & ((1 << idx) - 1)
high = mask >> (idx + 1)
child = low | (high << idx)
val &= dp[length - 1][child]
if not val:
break
cur[mask] = val
dp[length] = cur
out.write(str(((1 << n) + sum(dp[n])) % MOD) + "\n")
return out.getvalue()
# provided samples
assert run(
"""3
2 2
1
1
3 1
2
1 3
3 2
2
1 2
"""
) == "6\n1\n11\n"
# minimum size
assert run(
"""1
1 1
1
1
"""
) == "1\n"
# single pile with value 1 or 2
assert run(
"""1
1 2
1
1
"""
) == "3\n"
# only index 1 is good
assert run(
"""1
2 2
1
1
"""
) == "6\n"
# all indices good
assert run(
"""1
2 2
2
1 2
"""
) == "6\n"
| Test input | Expected output | What it validates |
|---|---|---|
n=1, m=1 |
1 |
No moves, unique configuration |
n=1, m=2 |
3 |
Both single-pile configurations counted |
n=2, good={1} |
6 |
Forced deletion path |
n=2, good={1,2} |
6 |
Multiple legal moves |
Edge Cases
Only one pile
Input:
1 2
1
1
The DP starts from length 1, so no transitions are performed.
The two masks are:
0 -> value 1
1 -> value 2
The answer is:
1 + 2 = 3
The algorithm handles this naturally because the base layer already represents finished games.
All piles equal to one
Input:
3 1
2
1 3
There is only one configuration:
[1,1,1]
No matter how the game proceeds, the final pile value is 1.
The algorithm immediately returns 1 when m = 1, avoiding unnecessary DP work.
Good indices disappearing as the sequence shrinks
Input:
3 2
2
1 3
When the current length becomes 2, index 3 is no longer valid.
The implementation explicitly keeps only good indices satisfying:
good_index <= current_length
so every generated move is legal in the current state. This avoids accessing non-existent positions and matches the game rules exactly.