SyntaxPilot
Courses/Competitive Programming/Lesson 30

Competitive Programming · Lesson 30 of 90 · 11 min

Game theory 1: winning and losing positions

queued

These are the notes for Competitive Programming episode 30, the start of game theory. A plate of laddoos at a family function (take 1, 2 or 3; whoever takes the last laddoo wins) shows how to work backwards from the end: 0 laddoos is a losing position for the player to move, 1–3 are winning, 4 is losing again, and the losing positions are exactly the multiples of 4. This gives the two definitions all of game theory is built on: a position is W if some move goes to an L position, and L if every move goes to a W position (or there is no move). An original problem, Coin Jar (take a power of 2 coins, n up to 10^18), shows the contest recipe: the W/L DP is correct but gets TLE (and a std::bad_alloc crash for 10^18), so we print the DP table for small n, spot the pattern (L exactly when n % 3 == 0), prove it, and stress test it. Part two flips the ending (misère play: the last coin loses) and the pattern shifts to n % 3 == 1. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook: the last laddoo

Ten laddoos on a plate. Two cousins take turns; each turn you take 1, 2 or 3. Whoever takes the last laddoo wins it. Both play perfectly. Should you go first?

laddoos 0 1 2 3 4 5 6 7 8 9
player to move L W W W L W W W L W
  • 0: you can't move; your cousin took the last one: L.
  • 1, 2, 3: take them all: W.
  • 4: any move leaves 3, 2 or 1, all W for your cousin: L.
  • 5, 6, 7: take just enough to leave 4: W.
  • With 10 laddoos, go first and take 2 (leaving 8, a multiple of 4).

General rule (take 1 to k): the losing positions are the multiples of k + 1.

Definitions

  • Two-player game with perfect information: both players see everything; no dice, no hidden cards.
  • Optimal play: both players always make the best possible move. Contest problems always assume it.
  • Position: everything that describes the game right now (here: the number of coins; whose turn it is is implied).
  • Normal play: a player who cannot move loses.
  • Winning position (W): the player to move can force a win: some move leads to an L position.
  • Losing position (L): every move leads to a W position, or there is no move at all.
  • Misère play: the player who makes the last move loses.

In code (for any finite game, one that can't go on forever):

win[i] = true  if any move i → j has win[j] == false
win[i] = false otherwise (including positions with no moves)

Label the game graph backwards: dead ends are L, anything with an arrow into an L is W, anything whose arrows all go into W's is L.

Problem G · Coin Jar

(Written for this course, in the style of a Codeforces Div. 2 problem.)

A jar holds n coins. Riya moves first, then Kabir, alternately. A move takes a power of 2 coins (1, 2, 4, 8, …), never more than are left. Whoever takes the last coin wins. Both play optimally. Print the winner for each jar.

  • Input: t (1 ≤ t ≤ 10^5), then t lines with n (1 ≤ n ≤ 10^18).
  • Output: Riya or Kabir per jar.
Input Output
4 / 1 3 7 9 Riya Kabir Riya Kabir

Brute force: the W/L DP

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int t;
    cin >> t;
    vector<ll> q(t);
    for (ll &n : q) cin >> n;
    ll N = *max_element(q.begin(), q.end());
    vector<bool> win(N + 1, false);   // win[0] = false: no move
    for (ll i = 1; i <= N; i++)
        for (ll p = 1; p <= i; p *= 2)     // take 1, 2, 4, 8, ...
            if (!win[i - p]) { win[i] = true; break; }
    for (ll n : q) cout << (win[n] ? "Riya" : "Kabir") << "\n";
    return 0;
}
Input Output
the sample Riya Kabir Riya Kabir ✓
1 / 1000000000 Time Limit Exceeded
1 / 1000000000000000000 terminate called after throwing an instance of 'std::bad_alloc'

Why: the DP visits every position with about log₂ n moves each (≈ 6 · 10^19 steps for 10^18) and stores one entry per position (10^18 bits is over 100,000 terabytes). std::bad_alloc is C++'s "out of memory" exception: the vector of 10^18 entries can't be allocated.

The contest trick: print the table, find the pattern

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N = 20;
    vector<bool> win(N + 1, false);
    for (int i = 1; i <= N; i++)
        for (int p = 1; p <= i; p *= 2)
            if (!win[i - p]) { win[i] = true; break; }
    for (int i = 0; i <= N; i++) cout << i << (win[i] ? "W " : "L ");
    return 0;
}

Output:

0L 1W 2W 3L 4W 5W 6L 7W 8W 9L 10W 11W 12L 13W 14W 15L 16W 17W 18L 19W 20W

Every third position is L. Guess: L exactly when n % 3 == 0.

Proof

  1. n % 3 == 0 → every move goes to W. A move removes 2^k coins, and 2^k is never a multiple of 3 (its only prime factor is 2). So n − 2^k is not a multiple of 3, which (by the claim) is W for the opponent.
  2. n % 3 != 0 → some move goes to L. If n % 3 == 1, take 1 coin; if n % 3 == 2, take 2. Both are powers of 2, and the opponent lands on a multiple of 3.
  3. The end, 0 coins, is a multiple of 3 and is L. So by induction the claim holds for every n.

Answer: Kabir if n % 3 == 0, else Riya, O(1) per jar.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        // L exactly when n is a multiple of 3
        cout << (n % 3 != 0 ? "Riya" : "Kabir") << "\n";
    }
    return 0;
}
Input Output
the sample Riya Kabir Riya Kabir
2 / 999999999999999999 / 1000000000000000000 Kabir Riya

10^18 = 999…9 + 1, so 10^18 % 3 == 1: Riya takes one coin and wins.

A stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N = 100000;
    vector<bool> win(N + 1, false);
    for (int i = 1; i <= N; i++)
        for (int p = 1; p <= i; p *= 2)
            if (!win[i - p]) { win[i] = true; break; }
    for (int n = 0; n <= N; n++)
        if (win[n] != (n % 3 != 0)) { cout << "mismatch at " << n; return 0; }
    cout << "all " << N + 1 << " positions match";
}

Output: all 100001 positions match.

Part 2 · Problem G2 · Last Coin Loses (misère)

(Written for this course.) Same jar and moves, but whoever takes the last coin loses. Sample: 4 / 1 2 4 5 → Kabir Riya Kabir Riya.

Reusing the normal answer prints Riya Riya Riya Riya: two of four wrong. Only the base case changes: with 0 coins on your turn, your opponent took the last coin and lost, so win[0] = true.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N = 20;
    vector<bool> win(N + 1, false);
    win[0] = true;    // the other player took the last coin
    for (int i = 1; i <= N; i++)
        for (int p = 1; p <= i; p *= 2)
            if (!win[i - p]) { win[i] = true; break; }
    for (int i = 0; i <= N; i++) cout << i << (win[i] ? "W " : "L ");
    return 0;
}

Output:

0W 1L 2W 3W 4L 5W 6W 7L 8W 9W 10L 11W 12W 13L 14W 15W 16L 17W 18W 19L 20W

The pattern slides by one: L exactly when n % 3 == 1. Proof: from remainder 1 every move (−1 or −2 mod 3, since 2^k ≡ 1 or 2 mod 3) leaves remainder 0 or 2; from remainder 0 take 2, from remainder 2 take 1, to reach remainder 1.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        // misère: L exactly when n % 3 == 1
        cout << (n % 3 != 1 ? "Riya" : "Kabir") << "\n";
    }
    return 0;
}

Output on the sample: Kabir Riya Kabir Riya.

coins 0 1 2 3 4 5 6 7 8 9
normal L W W L W W L W W L
misère W L W W L W W L W W

Complexity vs the constraints

Method Time Memory n = 10^18
W/L DP O(n log n) O(n) crash / TLE
DP table for n ≤ 20 tiny tiny a tool to find the pattern
n % 3 O(1) per jar O(1) instant

Common mistakes (and the real outputs)

Bug 1: the wrong base case

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int t;
    cin >> t;
    vector<ll> q(t);
    for (ll &n : q) cin >> n;
    ll N = *max_element(q.begin(), q.end());
    vector<bool> win(N + 1, false);
    win[0] = true;                     // "nothing left: I win?"
    for (ll i = 1; i <= N; i++)
        for (ll p = 1; p <= i; p *= 2)     // take 1, 2, 4, 8, ...
            if (!win[i - p]) { win[i] = true; break; }
    for (ll n : q) cout << (win[n] ? "Riya" : "Kabir") << "\n";
    return 0;
}

On the sample it prints Kabir Riya Kabir Riya: every answer flipped. In normal play, no move means you lost, so win[0] must be false. Every position is built from smaller ones, so one wrong base case breaks the whole table.

Bug 2: int n

With int n; and input 1 / 999999999999999999, the program prints Riya (expected Kabir). The value doesn't fit, so cin stores 2147483647, which is not a multiple of 3.

Bug 3: reusing the rule after the rules change

The normal-play formula on the misère sample prints Riya Riya Riya Riya (expected Kabir Riya Kabir Riya).

Summary table

Mistake What you see Why Fix
win[0] = true; in normal play every answer flipped no move means you lost win[0] = false
int n; Riya instead of Kabir 10^18 overflows an int long long n
normal rule on a misère game 2 of 4 samples wrong the base case flipped rebuild the table: n % 3 != 1
vector<bool> win(N + 1) for N = 10^18 std::bad_alloc 10^18 entries use the DP only to find the pattern
a pattern from 5 values, no proof WA on hidden tests patterns can change later prove it and stress test it

Mini project

Write a "game lab" program: given a set of allowed moves S (e.g. {1, 3, 4}), print the W/L table for n ≤ 60, detect the period automatically (the smallest p such that the table repeats with period p from some point on), and answer queries for n ≤ 10^18 using the period. Stress test it against the DP for n ≤ 10^5 with several move sets.

Practice

  1. Take 1, 3 or 4 coins. Find the losing positions.

    Answer Table: L W L W W W W L W L W W W W L … L exactly when <b>n % 7 is 0 or 2</b> (checked with the DP up to 30, period 7).

  2. Divisor game. A move subtracts any divisor d of n with 1 ≤ d < n. Who wins from n?

    Answer n = 1 has no move: L. Table for n ≥ 1: L W L W L W … The first player wins exactly when <b>n is even</b> (subtract 1 to give the opponent an odd number; an odd number only has odd divisors, so it always leaves an even number).

  3. Two jars, take 1, 2 or 3 coins from one jar. When does Riya win?

    Answer Riya wins exactly when <b>a % 4 != b % 4</b> (checked by brute force for a, b < 20). If the remainders are equal, copy the opponent's move on the other jar. Episode 31 explains why with Grundy numbers.

  4. Take 1 to k laddoos.

    Answer L exactly when <b>n % (k + 1) == 0</b>: from a multiple, any move leaves a non-multiple; from a non-multiple, take n % (k + 1). For k = 4: L at 0, 5, 10, …

Quick quiz

Moves: take 1, 3 or 4 coins; the last coin wins. Is n = 7 W or L?

A) W: take 1 · B) W: take 3 · C) L · D) W: take 4

Answer

C. Table: 0 L, 1 W, 2 L, 3 W, 4 W, 5 W, 6 W, 7 L. From 7 you can reach 6, 4 or 3: all W for the opponent.

Interview questions

  1. Define winning and losing positions. W: some move reaches an L position. L: every move reaches a W position (or none exists).
  2. What is normal play vs misère play? Normal: the player who can't move loses. Misère: the player who makes the last move loses.
  3. How do you solve a game with n up to 10^18? Compute W/L by DP for small n, find a pattern (often periodic), prove it, stress test it.
  4. Why must a game be finite for this DP? The backward labelling needs an order in which every move goes to an already-labelled position; a game that can loop forever can also end in a draw.
  5. In the take-1-to-k game, which positions lose? Multiples of k + 1.
  6. What does std::bad_alloc mean? C++ couldn't allocate the memory requested (for example a vector of 10^18 entries).

Glossary

Term Meaning Example
Game theory (combinatorial) Two players, alternate moves, full information, no luck the laddoo game
Optimal play Both players always make the best move contests assume it
Position Everything describing the game now 7 coins left
Move A legal change of position take 4 coins
Normal play No move left = you lose the last coin wins
Misère play The last move loses the last coin loses
Winning position (W) Some move goes to an L position 5 laddoos: take 1
Losing position (L) Every move goes to a W position, or no move 4 laddoos
Base case The value at the end of the game win[0] = false
Game graph Positions as dots, moves as arrows label backwards
Period / pattern The W/L table repeats L every 3rd coin
Proof by induction True at the base, and each step keeps it true multiples of 3 lose
Stress test Formula vs DP on many inputs all 100001 positions match
std::bad_alloc C++ out-of-memory exception a vector of 10^18

Summary

  • Work backwards from the end: W = some move to L; L = every move to W, or no move. Normal play: no move = L.
  • Take 1, 2 or 3: L at multiples of 4. Take a power of 2 (Coin Jar): L when n % 3 == 0 (proof: 3 never divides 2^k; 1 and 2 are powers of 2).
  • For huge n: DP on small n → pattern → proof → stress test (all 100001 positions match).
  • Misère flips the base case and shifts the pattern: L when n % 3 == 1.
  • Real bugs: win[0] = true (every answer flipped), int n (Riya instead of Kabir), the normal rule on a misère game.

Solutions in C++, Java and Python

Problem G · Coin Jar

C++: see "The accepted solution" above.

Java:

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine().trim());
            sb.append(n % 3 != 0 ? "Riya" : "Kabir").append('\n');
        }
        System.out.print(sb);
    }
}

Python:

import sys

data = sys.stdin.read().split()
t = int(data[0])
print("\n".join("Riya" if int(x) % 3 != 0 else "Kabir" for x in data[1:t + 1]))

Problem G2 · Last Coin Loses

Change the test to n % 3 != 1 in all three languages.