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:
RiyaorKabirper 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
- 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.
- 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.
- 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
-
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). -
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). -
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. -
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
- Define winning and losing positions. W: some move reaches an L position. L: every move reaches a W position (or none exists).
- 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.
- 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.
- 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.
- In the take-1-to-k game, which positions lose? Multiples of k + 1.
- What does
std::bad_allocmean? 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(Riyainstead ofKabir), 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.