Skip to content
Embercode
✕
Game theoryLesson 9 of 9

50 min read

Problem set

Why this matters when you build with AI

An AI tool will write a solution to a game problem quickly, and the code often passes the sample in the statement. The sample is small, so it hides the common errors: a wrong window length, a missing draw label, a Nim shortcut applied to misere play. A solution is only trusted after it agrees with a brute force program on many small random inputs.

This set gives ten problems that use the tools from the module. Each one comes with a statement, limits on the input, a sample, a worked solution, and the output of that solution on the sample. Each solution in this lesson was compiled with g++ -std=c++17 -O2 -Wall -Wextra and compared with a brute force on 300 random small inputs. The brute force is a plain recursion over game states with a memo table, and it never uses the formulas.

Some terms used below. A position is the state of the game when one player is to move. A P-position is one where the player to move loses with perfect play. An N-position is one where the player to move wins. The Grundy value of a position is a number that adds up across independent games by XOR. A mex of a set is the smallest non-negative integer not in the set. A brute force is a search over every possibility with no shortcut.

How to work through the set

Read a statement, then try to answer on paper for the sample. Next write a brute force in your own scratch folder. Then write the fast solution and compare the two on random small inputs. Only after that, read the worked solution and compare its reasoning with yours.

Each input is given as plain integers. Read them with cin in C++ or input in Python, and print one answer per line unless the statement says otherwise. Use long long for any value that can reach 10^9 or more.

Problem 1: Ladder count

A pile of stones is shared by two players. A move removes exactly k stones, where k is one of m allowed amounts. The player who cannot move loses. For each query n, print how many P-positions there are among the heaps of size 0, 1, up to n.

Constraints

  • 1 ≤ m ≤ 5. Each allowed amount is an integer from 1 to 20, and the amounts are distinct.
  • 1 ≤ q ≤ 200000 queries. Each query n satisfies 0 ≤ n ≤ 10^6.

Input is the value m, a line with the m amounts, the value q, and a line with the q queries.

Sample

2
2 5
4
0 1 4 12

Solution

The solution fills the table of winning and losing heaps up to the largest query by backward induction. Then it keeps a running count of P-positions, so every query is answered in constant time.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int m;
    cin >> m;
    vector<int> moves(m);
    for (int &x : moves) cin >> x;
    int q;
    cin >> q;
    vector<int> qs(q);
    int maxn = 0;
    for (int &x : qs) {
        cin >> x;
        maxn = max(maxn, x);
    }
 
    // win[n] is 1 when the player to move with n stones wins.
    vector<char> win(maxn + 1, 0);
    for (int n = 0; n <= maxn; ++n)
        for (int k : moves)
            if (k <= n && !win[n - k]) {
                win[n] = 1;
                break;
            }
 
    // cnt[n] is the number of P-positions in [0, n].
    vector<int> cnt(maxn + 1, 0);
    for (int n = 0; n <= maxn; ++n)
        cnt[n] = (n ? cnt[n - 1] : 0) + (win[n] ? 0 : 1);
 
    for (int n : qs) cout << cnt[n] << "\n";
    return 0;
}

Output of the sample, from the compiled program:

1
2
3
6

The P-positions for amounts 2 and 5 are 0, 1, 4, 7, 8 and 11. Among heaps 0 to 12, the counts for 0, 1, 4 and 12 are 1, 2, 3 and 6.

Checks and complexity

The random comparison used 300 cases with amounts up to 8 and heaps up to 40. The brute force is a recursion over heap sizes with a memo table. There were 0 mismatches. Time is O(maxn * m) and memory is O(maxn). With the largest limits that is about 5 million steps for the table.

Problem 2: Capped Nim

There are n piles of stones. On a turn, a player picks one pile and removes between 1 and K stones from it. A player who cannot move loses. Print First if the first player wins with perfect play, otherwise Second.

Constraints

  • 1 ≤ n ≤ 100000, 1 ≤ K ≤ 10^9.
  • Each pile a satisfies 0 ≤ a ≤ 10^9.

Input is a first line with n and K, then a line with the n piles.

Sample

3 2
3 5 6

Solution

A single pile of size a has a Grundy value of a mod K + 1. The proof is short. Let r be a mod K + 1. If a is at most K, the options are the piles 0 to a - 1, which have values 0 to a - 1, so the mex is a, which is r. If a is larger than K, the options are the piles a - K to a - 1. Those K consecutive sizes have K different residues mod K + 1, and none of them is r. So the set of option values is every value in 0 to K except r, and its mex is r. Since a move changes one pile only, the piles are independent games, and their Grundy values combine by XOR, as shown in the Sprague-Grundy lesson.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    long long K;
    cin >> n >> K;
    long long x = 0;
    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;
        // Grundy value of one pile of size a in capped Nim is a mod (K + 1).
        x ^= a % (K + 1);
    }
    cout << (x != 0 ? "First" : "Second") << "\n";
    return 0;
}

Output of the sample, from the compiled program:

First

The values are 3 mod 3 = 0, 5 mod 3 = 2 and 6 mod 3 = 0. Their XOR is 2, which is not 0, so the first player wins.

Checks and complexity

The random comparison used 300 cases with up to 3 piles of size up to 6 and K up to 3. There were 0 mismatches. Time is O(n).

Problem 3: Misere Nim

Standard Nim is played with piles of stones, where a move removes at least one stone from one pile. In this variant, the player who takes the last stone loses. So a player who finds no stones left has won. Print the winner with perfect play.

Constraints

  • 1 ≤ n ≤ 100000.
  • Each pile a satisfies 0 ≤ a ≤ 10^9.

Input is n, then a line with the n piles.

Sample

2
1 1

Solution

The misere rule has two cases. If some pile has 2 or more stones, the first player wins exactly when the XOR of the piles is not 0, which is the same as in standard Nim. If every pile has 0 or 1 stones, the game is decided by parity: the first player wins when the number of piles of size 1 is even. Check the second case by hand. With no 1-piles, the first player cannot move and wins. With one 1-pile, the first player must take it and loses.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    long long x = 0;
    long long ones = 0;
    bool big = false;
    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;
        x ^= a;
        if (a == 1) ++ones;
        if (a >= 2) big = true;
    }
    bool first_wins;
    if (big)
        first_wins = (x != 0);  // some pile has 2 or more: misere play follows the normal XOR rule
    else
        first_wins = (ones % 2 == 0);  // every pile is 0 or 1: the count of 1-piles decides
    cout << (first_wins ? "First" : "Second") << "\n";
    return 0;
}

Output of the sample, from the compiled program:

First

For the sample 1 1, the standard XOR rule would print Second, because 1 XOR 1 is 0. The misere answer is First: the first player takes one stone, the second player must take the other, and loses.

Checks and complexity

The random comparison used 300 cases with up to 4 piles of size up to 4. There were 0 mismatches. Time is O(n).

Problem 4: Take-or-split heaps

Each heap has h coins. On a turn, a player does exactly one of three things to one heap. The player removes one coin. Or the player removes two coins. Or, when h is at least 3, the player removes one coin and splits the remaining h - 1 coins into two non-empty heaps of sizes a and b, with a + b = h - 1. The player who cannot move loses. Print First or Second for the starting heaps.

Constraints

  • 1 ≤ k ≤ 100 heaps. Each heap size h satisfies 0 ≤ h ≤ 300.

Input is k, then a line with the k heap sizes.

Sample

3
1 2 3

Solution

The Grundy value of a heap of size n is the mex of the values of its options. The value of an option is the XOR of the values of the heaps it leaves. The values are computed for every size from 0 to 300 in increasing order, so each option refers only to smaller sizes. The sum of heaps is then won by the first player if the XOR of their values is not 0.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    const int MAXN = 300;
    vector<int> g(MAXN + 1, 0);
    for (int n = 1; n <= MAXN; ++n) {
        vector<int> opts;
        opts.push_back(g[n - 1]);  // take 1 coin
        if (n >= 2) opts.push_back(g[n - 2]);  // take 2 coins
        if (n >= 3)  // take 1 coin, then split the other n - 1 coins into two non-empty heaps
            for (int a = 1; a <= n - 2; ++a) {
                int b = n - 1 - a;
                opts.push_back(g[a] ^ g[b]);
            }
        sort(opts.begin(), opts.end());
        opts.erase(unique(opts.begin(), opts.end()), opts.end());
        int mex = 0;
        while (mex < (int)opts.size() && opts[mex] == mex) ++mex;
        g[n] = mex;
    }
 
    int k;
    cin >> k;
    int x = 0;
    for (int i = 0; i < k; ++i) {
        int s;
        cin >> s;
        x ^= g[s];
    }
    cout << (x != 0 ? "First" : "Second") << "\n";
    return 0;
}

Output of the sample, from the compiled program:

Second

The values for heaps 0, 1, 2 and 3 are 0, 1, 2 and 3. The split of a 3-heap into 1 and 1 gives 1 XOR 1 = 0, but the take options already give 2 and 1, so the mex is 3. The sample has 1 XOR 2 XOR 3 = 0, so the second player wins.

Checks and complexity

The random comparison used 300 cases with up to 3 heaps of size up to 6. The brute force builds the same options directly from the rules and searches the game without any Grundy values. There were 0 mismatches. Building the table costs O(MAXN^2), about 90000 steps, and each query costs O(k).

Problem 5: Token on a directed graph

A directed graph has n vertices numbered 0 to n - 1. A token sits on a vertex. On a turn, the player to move must move the token along one outgoing edge. A player with no outgoing edge loses. A game that never ends is a draw. For each vertex, print W if the player to move there wins, L if the player to move loses, and D if the game is a draw with perfect play. Multiple edges and self-loops are allowed.

Constraints

  • 1 ≤ n ≤ 200000, 0 ≤ m ≤ 400000.
  • Each edge is given as two vertex numbers u and v, meaning an edge from u to v.

Input is n and m, then m lines with u and v. Output is one line of n characters.

Sample

5 5
0 1
1 2
2 1
2 3
3 4

Solution

This is retrograde analysis. It starts from the losing vertices, which have no outgoing edges. Whenever a vertex is known to be losing, each vertex with an edge into it is winning. Whenever a vertex is known to be winning, its predecessors lose one unknown option. A predecessor becomes losing when all its options are winning. The queue runs until it is empty. Vertices never labelled stay in a cycle with no forced end, so they are draws.

The count of options is per edge, not per distinct target. That keeps multiple edges correct.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> pred(n);  // pred[v] lists u once for every edge u -> v
    vector<int> cnt(n, 0);        // number of out-edges of v not yet known to lead to L
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        pred[v].push_back(u);
        cnt[u]++;
    }
 
    // lab: 0 = unknown (draw so far), 1 = W (player to move wins), 2 = L (player to move loses).
    vector<int> lab(n, 0);
    queue<int> q;
    for (int v = 0; v < n; ++v)
        if (cnt[v] == 0) {
            lab[v] = 2;  // no move: the player to move loses
            q.push(v);
        }
 
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : pred[v]) {
            if (lab[u] != 0) continue;
            if (lab[v] == 2) {  // u can move to a losing vertex
                lab[u] = 1;
                q.push(u);
            } else if (--cnt[u] == 0) {  // every move of u leads to W
                lab[u] = 2;
                q.push(u);
            }
        }
    }
 
    string s;
    for (int v = 0; v < n; ++v) s += (lab[v] == 1 ? 'W' : lab[v] == 2 ? 'L' : 'D');
    cout << s << "\n";
    return 0;
}

Output of the sample, from the compiled program:

DDDWL

Vertex 4 has no outgoing edge, so it is L. Vertex 3 has an edge to 4, so it is W. Vertices 1 and 2 form a cycle, and 2 also has an edge to 3, which is winning for the player who moves there. Neither 1 nor 2 can be forced to a losing vertex, so both are draws. Vertex 0 leads only into the cycle, so it is a draw too.

Checks and complexity

The random comparison used 300 graphs with up to 6 vertices and 9 edges, self-loops and repeated edges included. The brute force repeats the rules as a fixpoint: it labels a vertex W when some option is L, labels it L when every option is W, and stops when nothing changes. There were 0 mismatches. Time is O(n + m).

Problem 6: Misere two piles

There are two piles of stones of sizes a and b. On a turn, a player removes 1 or 2 stones from one pile. This is misere play: the player who takes the last stone loses, so a player with no move left has won. Print the winner for each query.

Constraints

  • 1 ≤ t ≤ 10000 queries. Each pile satisfies 0 ≤ a, b ≤ 300.

Input is t, then t lines with a and b.

Sample

3
1 1
2 0
3 4

Solution

The table win[a][b] is filled in row order. A move from (a, b) reaches a pair with one pile smaller, and both such pairs come earlier in the loops. The only position with no move is (0, 0), and in misere play the player to move there has won.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    const int MAXV = 300;
    // win[a][b] is 1 when the player to move with piles a and b wins under misere play.
    static char win[MAXV + 1][MAXV + 1];
    for (int a = 0; a <= MAXV; ++a)
        for (int b = 0; b <= MAXV; ++b) {
            if (a == 0 && b == 0) {  // no stones left: the opponent took the last one and loses
                win[a][b] = 1;
                continue;
            }
            bool w = false;
            if (a >= 1 && !win[a - 1][b]) w = true;
            if (a >= 2 && !win[a - 2][b]) w = true;
            if (b >= 1 && !win[a][b - 1]) w = true;
            if (b >= 2 && !win[a][b - 2]) w = true;
            win[a][b] = w;
        }
 
    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        cout << (win[a][b] ? "First" : "Second") << "\n";
    }
    return 0;
}

Output of the sample, from the compiled program:

First
First
Second

For (1, 1) the first player takes one stone from a pile and leaves (0, 1). The second player must take that last stone. Then the first player has no move, which under misere play is a win. So (1, 1) is First, and the table gives (0, 1) as a loss for the player to move.

Checks and complexity

The random comparison used 300 cases of up to 4 pairs with piles up to 6. The brute force is a recursion over pairs with a memo and the terminal rule written out separately. There were 0 mismatches. The table costs about 90000 steps, and each query costs O(1).

Problem 7: Mirror board

A square board has n rows and n columns, numbered from 1. Some cells are blocked. Two players alternately place a token on any free cell, and a placed token is never moved. The player who cannot place a token loses. The blocked set is symmetric through the centre: if (r, c) is blocked, then (n + 1 - r, n + 1 - c) is blocked too. Print First or Second.

Constraints

  • 1 ≤ n ≤ 10^9, 0 ≤ k ≤ 200000 blocked cells.
  • Each blocked cell satisfies 1 ≤ r, c ≤ n. The input is guaranteed symmetric.

Input is a first line with n and k, then k lines with r and c.

Samples

3 2
1 1
3 3
3 1
2 2

Solution

The mirror of a free cell is free too, because the blocked set is symmetric and the tokens placed so far are symmetric. So the second player can always answer a move with its mirror image, except when the move is on the centre cell, which is its own mirror. A board with odd n has a centre. If the centre is free, the first player takes it at once, and then the first player is the one who mirrors. Otherwise the second player always has a mirror reply.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    long long n;
    int k;
    cin >> n >> k;
    long long mid = (n + 1) / 2;
    bool centre_blocked = false;
    for (int i = 0; i < k; ++i) {
        long long r, c;
        cin >> r >> c;
        if (n % 2 == 1 && r == mid && c == mid) centre_blocked = true;
    }
    // The blocked set is symmetric. If the centre cell exists and is free, the first player
    // takes it and answers every later move with its mirror image. Otherwise every free cell
    // has a different mirror image, so the second player can do the same.
    bool first_wins = (n % 2 == 1) && !centre_blocked;
    cout << (first_wins ? "First" : "Second") << "\n";
    return 0;
}

Output of the two samples, from the compiled program:

First
Second

In the first sample the centre (2, 2) is free, so First wins. In the second sample the only blocked cell is the centre, so no free cell is its own mirror and Second wins.

Checks and complexity

The random comparison used 300 boards with n from 1 to 4. Each blocked set was built by choosing mirror pairs at random, so the centre was blocked in some cases and free in others. The brute force searches over sets of occupied cells with a memo and no symmetry rule. There were 0 mismatches. Time is O(k).

Problem 8: Picking items for the best difference

There are n items with values v. Two players alternately take one item from the items that remain. Each player wants to maximise their own total minus the other player's total. Print that best difference for the first player, meaning the first player's total minus the second player's total under best play.

Constraints

  • 1 ≤ n ≤ 16. Each value satisfies 1 ≤ v ≤ 10^9.

Input is n, then a line with the n values.

Sample

3
1 5 2

Solution

A state is the set of items already taken, stored as a bitmask. Let dp[mask] be the best difference, from the view of the player to move, over the items not in mask. Taking item i gives v[i] to the mover, and then the opponent plays from the new state, so the mover's gain is v[i] - dp[mask | bit i]. The mover takes the maximum over i. The masks are processed from the full mask down to 0, so every state that is needed is already filled.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<long long> v(n);
    for (auto &x : v) cin >> x;
 
    int full = (1 << n) - 1;
    // mask holds the items already taken. dp[mask] is the best value of
    // (mover's total minus other player's total) over the items not in mask.
    vector<long long> dp(1 << n, 0);
    for (int mask = full; mask >= 0; --mask) {
        if (mask == full) {
            dp[mask] = 0;
            continue;
        }
        long long best = LLONG_MIN;
        for (int i = 0; i < n; ++i)
            if (!((mask >> i) & 1)) best = max(best, v[i] - dp[mask | (1 << i)]);
        dp[mask] = best;
    }
    cout << dp[0] << "\n";
    return 0;
}

Output of the sample, from the compiled program:

4

The best line is: the first player takes 5, the second takes 2, and the first takes 1. The first player gets 6 and the second gets 2, so the difference is 4. The brute force checks that no other line does better.

Checks and complexity

The random comparison used 300 cases with up to 6 items of value 1 to 9. The brute force plays every line of the game, adds the real totals, and takes the best result, with no memo table. There were 0 mismatches. Time is O(2^n * n), about 1 million steps at n = 16. Memory is O(2^n) values of 8 bytes each, which is 512 KB at n = 16.

Problem 9: Dividing cards

The cards 1 to n lie on a table. On a turn, a player picks a card i that is still on the table. The pick removes card i and every card still on the table whose number divides i. A player with no card to pick loses. For each n, print First if the first player wins from the full set of cards 1 to n, otherwise Second.

Constraints

  • 1 ≤ t ≤ 100 queries. Each n satisfies 1 ≤ n ≤ 18.

Input is t, then t lines with n.

Samples

3
1
2
3

Solution

The state is the set of cards on the table, stored as an 18-bit mask. The solver fills every mask once, from 1 upward. A pick of card i leads to the mask with the divisors of i removed. That mask is smaller, because it loses at least card i, so it was already filled.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    const int N = 18;
    // div[i] has bit (j - 1) set when j divides i. It includes i itself.
    vector<int> div(N + 1, 0);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= i; ++j)
            if (i % j == 0) div[i] |= 1 << (j - 1);
 
    // win[mask] is 1 when the player to move, facing the cards in mask, wins.
    const int full = 1 << N;
    vector<char> win(full, 0);
    for (int mask = 1; mask < full; ++mask)
        for (int i = 1; i <= N; ++i) {
            if (!((mask >> (i - 1)) & 1)) continue;
            if (!win[mask & ~div[i]]) {
                win[mask] = 1;
                break;
            }
        }
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << (win[(1 << n) - 1] ? "First" : "Second") << "\n";
    }
    return 0;
}

Output of the sample, from the compiled program:

First
First
First

For n = 1, the first player takes card 1 and the table is empty. For n = 2, taking card 2 also removes card 1, because 1 divides 2, so the table is empty again. For n = 3, picking card 1 leaves the cards 2 and 3, which is a losing set for the player to move.

Checks and complexity

The random comparison used 300 cases of up to 5 queries with n from 1 to 7. The brute force keeps the table as a set of numbers and uses a memo over those sets. There were 0 mismatches. The table build for N = 18 ran in 0.02 seconds and used about 4 MB on this machine, measured with /usr/bin/time. Time is O(2^N * N), about 4.7 million steps.

Problem 10: Subtraction piles with allowed amounts

There are n piles. A move removes k stones from one pile, where k is in the allowed set S, and k must not be more than the pile holds. The player who cannot move loses. Print First or Second for the starting piles.

Constraints

  • 1 ≤ m ≤ 3 allowed amounts, each from 1 to 10 and distinct.
  • 1 ≤ n ≤ 200000 piles. Each pile satisfies 0 ≤ a ≤ 10^5.

Input is m, a line with the amounts, n, and a line with the piles.

Sample

2
1 3
2
4 5

Solution

Each pile is a separate game, so the piles combine by XOR of their Grundy values. The Grundy value of a pile of x stones is the mex of the values of the piles x - k for allowed k that fit. Values are filled from small to large, so each option is already known.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int m;
    cin >> m;
    vector<int> S(m);
    for (int &s : S) cin >> s;
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
 
    int maxa = *max_element(a.begin(), a.end());
    // g[x] is the Grundy value of one pile of x stones.
    vector<int> g(maxa + 1, 0);
    for (int x = 1; x <= maxa; ++x) {
        vector<int> opts;
        for (int s : S)
            if (s <= x) opts.push_back(g[x - s]);
        sort(opts.begin(), opts.end());
        opts.erase(unique(opts.begin(), opts.end()), opts.end());
        int mex = 0;
        while (mex < (int)opts.size() && opts[mex] == mex) ++mex;
        g[x] = mex;
    }
 
    int total = 0;
    for (int x : a) total ^= g[x];
    cout << (total != 0 ? "First" : "Second") << "\n";
    return 0;
}

Output of the sample, from the compiled program:

First

With allowed amounts 1 and 3, the Grundy values of piles 0 to 5 are 0, 1, 0, 1, 0, 1. The piles 4 and 5 have values 0 and 1, and their XOR is 1, so the first player wins.

Checks and complexity

The random comparison used 300 cases with up to 3 allowed amounts from 1 to 4 and up to 3 piles of size up to 6. The brute force searches the game over sorted pile tuples with a memo, and it never builds Grundy values. There were 0 mismatches. Time is O(maxa * m).

Common mistakes the set is built to catch

Using the parity rule for capped Nim. A quick guess is to XOR the piles mod 2. With K = 2 and one pile of size 2, that rule gives Second, because 2 mod 2 is 0. The real answer is First: the player takes both stones and the opponent has no move. The correct value is a mod (K + 1), which is 2 mod 3 = 2. The compiled program prints First for the input 1 2 then 2.

Using the normal Nim rule for misere play. On the input 2 then 1 1, the XOR rule gives 1 XOR 1 = 0, so it prints Second. The misere answer is First. The program in Problem 3 prints First. Always check the terminal rule first: in misere play the player with no move has won.

Forgetting the centre cell in the mirror argument. A naive rule says that an odd board is a first-player win. On the sample 3 1 then 2 2, that rule prints First. But the centre is blocked, so the first player has no mirror-breaking move, and the answer is Second. The program prints Second.

Reading the sum as int. In Problem 8, 16 values of 10^9 add up to 1.6 times 10^10, which does not fit in a 32-bit int. The overflowed value is a wrong answer with no error message. Use long long for all sums of values.

Running a brute force at the largest limit. The brute forces in this set are for small inputs. A recursion of depth 10^5 or a memo over 2^200000 states will crash or never finish. Use the brute force only to check the formula or table on small inputs.

Trusting one passing sample. The samples in this set are small, so a wrong rule can still pass them. Run the random comparison before you trust a solution.

Checklist to keep

  • Write a brute force first, and compare the fast solution with it on at least a few hundred random small inputs.
  • For misere play, state the terminal rule before anything else.
  • For capped and subtraction piles, compute the Grundy values from the rule and look for the pattern, not a guess.
  • For graph games with cycles, label draws by a queue that stops, and do not count a draw as a loss.
  • For symmetric boards, check whether a fixed point exists before you apply the mirror argument.
  • Use long long for sums, and check the limits on the input before choosing an array size.

Hands-on exercise

Pick problems 1 and 10 and write a small Python generator that prints random inputs in the format of the statement. For each input, run the solution and a brute force and compare the outputs. Stop at the first mismatch and print it.

Then change problem 1 so that it counts the N-positions instead of the P-positions, and run the same loop. A good answer prints, for every query, n + 1 minus the P-count, since the N-positions are the rest of the heaps from 0 to n. A weak answer changes the print line without checking the result.

Prompt to try with an AI tool

Use this prompt, then check the answer against the brute force of Problem 2.

Write a C++17 program for capped Nim. The first line has n and K, with n piles up to 100000
and 1 at most K at most 10^9. The second line has the n pile sizes, each up to 10^9. A move
removes between 1 and K stones from one pile. The player who cannot move loses. Print First
or Second. Use the Grundy value of a pile and explain in two sentences why it has that value.
Then show the output for the input "3 2" followed by "3 5 6".

A good answer gives a mod (K + 1) for the pile value, uses long long, and prints First for the last line. Check the proof: the answer must say why the options cover every residue except a mod (K + 1). A weak answer gives the parity rule, which prints Second on the sample.

Practice

These take a few minutes each. Try them on paper or in your scratch folder before opening the answers.

Practice 1: capped Nim with K = 3

For capped Nim with K = 3, which single pile sizes from 0 to 12 are losing for the player to move?

Hint: The Grundy value of a single pile is the pile size mod 4, so a losing pile has value 0.

Show the answer

The losing piles are 0, 4, 8 and 12. The Grundy values for 0 to 12 are 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, from a Python run of the mex rule, which matches the pile size mod 4. A single pile of 4 is a losing position for the player to move, the same as an empty pile.

Practice 2: piles 2 and 5 with allowed amounts 1 and 3

Use Problem 10 to say whether the first player wins with piles 2 and 5 when the allowed amounts are 1 and 3.

Hint: Compute the Grundy values of the piles 2 and 5 separately, then XOR them.

Show the answer

The compiled program prints First. The Grundy values are 0 for pile 2 and 1 for pile 5, so their XOR is 1, which is not 0. The first player takes one stone from pile 5, which leaves piles 2 and 4, with values 0 and 0 and XOR 0.

Practice 3: a symmetric board with a free centre

Board size n = 5. The blocked cells are (1, 2) and (5, 4). Use Problem 7 to say who wins.

Hint: Check that the blocked set is symmetric, then check the centre (3, 3).

Show the answer

The mirror of (1, 2) is (5, 4), so the set is symmetric. The centre (3, 3) is free, so the first player takes it and then answers each move with its mirror. The compiled program prints First.

Practice 4: the best difference for four items

For the values 1 2 3 4, the best difference for the first player is what? Solve it by brute force on paper or in your scratch folder, then compare with Problem 8.

Hint: Try the line where the first player takes 4 first, and the line where the first player takes 1 first.

Show the answer

The answer is 2. The first player takes 4. The second player's best reply is to take 3, after which the first player takes 2 and the second takes 1. That gives the first player 6 and the second 4, a difference of 2. The other replies give the first player 4, so the second player avoids them. The compiled program prints 2.

Practice 5: two stones per pile in misere play

Two piles have sizes (2, 0) and each move removes 1 or 2 stones from one pile. Using Problem 6, say who wins under misere play, and explain why the answer differs from normal play.

Hint: Under normal play, the player who takes the last stone wins.

Show the answer

The compiled program prints First for (2, 0). Taking both stones is a mistake in misere play: the second player then has no move and wins. Taking one stone is correct. The second player must take the last stone and loses. Under normal play the first player wins by taking both stones, so the two rules agree on the answer for different moves.

Summary

Each problem reduces to a small set of tools: a table filled in increasing order, the mex and XOR of Grundy values, a queue for draws on graphs, a rule for misere play, a mirror argument for symmetry, or a bitmask DP over the set of items or cards left. The fast solution is only trusted after it matches a brute force on many random small inputs. The brute force is cheap to write, and it catches the common errors that a sample cannot.

Sources and scope

The theory used here is standard in combinatorial game theory. Bouton's analysis of Nim is in C. L. Bouton, "Nim, a Game with a Complete Mathematical Theory", Annals of Mathematics, second series, 1901 to 1902. The Sprague-Grundy and misere material is covered in E. R. Berlekamp, J. H. Conway and R. K. Guy, "Winning Ways for Your Mathematical Plays", 1982.

The ten problems, their statements and their tests were written for this lesson. None of them is copied from a judge.

All compiled code was built with g++ 15.2.0 on Linux (WSL2) with -std=c++17 -O2 -Wall -Wextra. The brute force scripts and the random comparisons used Python 3.14.4. Each problem was compared on 300 random cases with a fixed seed, and there were 0 mismatches in every problem. Only the bitmask solver in Problem 9 was timed at its largest limit, which took 0.02 seconds on this machine. The other limits were not timed at their maximum, so the time claims there are from the complexity analysis. The outputs on other machines will be the same, because the programs use no randomness.

Practice this topic: coding problems for Game theory →
← What the opponent can force