These are the notes for Competitive Programming episode 31. Episode 30 solved one coin jar with winning and losing positions. An original problem, Many Jars, puts many jars on the table (a move takes a power of 2 coins from one jar), and W/L labels stop working: counting the winning jars gets two of three samples wrong, and a brute force over every combination of jars is right but gets TLE at three jars of 300. The classic game Nim (take any number from one plate) shows the way: the player to move loses exactly when the XOR of the plates is 0. Then mex (the smallest missing number) gives every position a Grundy number, a position with Grundy number g plays exactly like a Nim plate of g, and the Sprague-Grundy theorem says a sum of games has the XOR of the Grundy numbers. A printed Grundy table shows g(n) = n % 3 for one jar, so the answer is the XOR of ai % 3. A stress test against the brute force passes 500 random tables. 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.
Problem H · Many Jars
(Written for this course, in the style of a Codeforces Div. 2 problem.)
n jars; jar i holds ai coins. Riya moves first, then Kabir, alternately. A move: choose one jar and take a power of 2 coins from it (1, 2, 4, …, not more than it holds). Whoever takes the very last coin on the table wins. Both play optimally.
- Input: t test cases; each has n (1 ≤ n ≤ 10^5) and a1 … an (0 ≤ ai ≤ 10^18).
- Output:
RiyaorKabirper test.
| Jars | Winner |
|---|---|
| 1 2 3 | Riya |
| 1 4 | Kabir |
| 4 5 | Riya |
Input format of the sample: 3 / 3 / 1 2 3 / 2 / 1 4 / 2 / 4 5.
The obvious attempt: count the winning jars
From episode 30, one jar is W when a % 3 != 0. Guess: Riya wins when the number of W jars is odd.
#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--) {
int n;
cin >> n;
int winJars = 0; // episode 30: jar is W if a % 3 != 0
for (int i = 0; i < n; i++) {
ll a;
cin >> a;
if (a % 3 != 0) winJars++;
}
cout << (winJars % 2 == 1 ? "Riya" : "Kabir") << "\n";
}
return 0;
}
Output on the sample: Kabir Kabir Kabir (expected Riya Kabir Riya). Counter-example by hand: jars 1 and 2 are both W. Riya takes 1 coin from the 2-jar, leaving (1, 1); Kabir must empty one jar and Riya takes the last coin. Two W jars made a W table. A W/L label is one bit of information, and a sum of games needs more.
Brute force over the whole table (Time Limit Exceeded)
The state is the whole sorted list of jars, memoised in a map:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map<vector<ll>, bool> memo;
bool win(vector<ll> a) { // every jar, every move
sort(a.begin(), a.end());
if (memo.count(a)) return memo[a];
bool res = false; // no move → L
for (int i = 0; i < (int)a.size() && !res; i++)
for (ll p = 1; p <= a[i] && !res; p *= 2) {
vector<ll> b = a;
b[i] -= p; // take p coins from jar i
if (!win(b)) res = true;
}
return memo[a] = res;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
cout << (win(a) ? "Riya" : "Kabir") << "\n";
}
return 0;
}
| Input | Output |
|---|---|
| the sample | Riya Kabir Riya ✓ |
1 / 3 / 300 300 300 |
Time Limit Exceeded |
The number of states is the product of the jar sizes (millions for three jars of 300, astronomically many for 10^5 jars of 10^18).
Nim and the XOR rule
Nim: several plates of laddoos; a move takes any number (at least 1) from one plate; the last laddoo wins.
Rule (Bouton's theorem): the player to move loses exactly when a1 ^ a2 ^ … ^ an == 0 (^ is XOR, episode 17).
Example: plates 3, 4, 5 → 011 ^ 100 ^ 101 = 010 = 2 ≠ 0, so the first player wins. Winning move: find a plate p with p ^ x < p (x = 2): 3 ^ 2 = 1 < 3, so take 2 from the 3-plate, leaving 1, 4, 5 with XOR 0.
Proof.
- All plates empty: XOR 0 and the player to move has lost. ✓
- From XOR 0, a move changes exactly one plate, which changes the XOR: it becomes non-zero.
- From XOR x ≠ 0, take x's highest 1 bit. Some plate p has a 1 in that bit, so p ^ x < p. Shrink that plate to p ^ x; the new XOR is x ^ p ^ (p ^ x) = 0.
So XOR-0 positions only reach non-zero positions, and non-zero positions can always reach 0: exactly the L/W definitions.
mex and Grundy numbers
mex (minimum excluded value) of a set of non-negative integers = the smallest one not in the set. A cricket team with jersey numbers 0, 1, 3 gives a new player number 2: mex{0, 1, 3} = 2. mex{} = 0.
Grundy number of a position: g(position) = mex{ g(option) : over all moves }.
- No moves: g = mex{} = 0.
- g = 0 ⇔ L (no option has Grundy 0), g ≠ 0 ⇔ W (by mex, some option has Grundy 0).
- A Nim plate of size s has options 0 … s − 1, so its Grundy number is s.
- A position with Grundy number g behaves exactly like a Nim plate of g: mex guarantees it can move to every value below g; a move to a higher value can be reversed by the opponent, so it never helps.
The Sprague-Grundy theorem
A sum of games: several games side by side; each turn the player moves in exactly one of them; the player who can't move anywhere loses.
g(game 1 + game 2 + … + game n) = g1 ^ g2 ^ … ^ gn
The first player wins exactly when this XOR is non-zero. Recipe: (1) find each component's Grundy number, usually from a small table and a pattern; (2) XOR them.
The Grundy table for one jar
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N = 20;
vector<int> g(N + 1);
for (int i = 0; i <= N; i++) {
set<int> seen; // Grundy numbers of the options
for (int p = 1; p <= i; p *= 2) seen.insert(g[i - p]);
int mex = 0; // smallest number not seen
while (seen.count(mex)) mex++;
g[i] = mex;
}
for (int i = 0; i <= N; i++) cout << g[i] << " ";
return 0;
}
Output: 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2, so g(a) = a % 3.
| coins | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| options' g | – | {0} | {1,0} | {2,1} | {0,2,0} | {1,0,1} | {2,1,2} | {0,2,0} | {1,0,1,0} | {2,1,2,1} |
| g = mex | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
Proof: 2^k ≡ 1 or 2 (mod 3), never 0, so from remainder r the options have remainders r − 1 and r − 2 (mod 3), never r; and the moves 1 and 2 reach both smaller remainders. So the mex is exactly r.
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--) {
int n;
cin >> n;
ll x = 0; // XOR of the Grundy numbers
for (int i = 0; i < n; i++) {
ll a;
cin >> a;
x ^= a % 3; // g(a) = a % 3
}
cout << (x != 0 ? "Riya" : "Kabir") << "\n";
}
return 0;
}
| Input | Output |
|---|---|
| the sample | Riya Kabir Riya (1 ^ 2 ^ 0 = 3; 1 ^ 1 = 0; 1 ^ 2 = 3) |
1 / 3 / 300 300 300 |
Kabir (instant) |
2 / 1 / 1000000000000000000 / 4 / 3 6 9 999999999999999999 |
Riya Kabir |
A stress test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map<vector<ll>, bool> memo;
bool win(vector<ll> a) {
sort(a.begin(), a.end());
if (memo.count(a)) return memo[a];
bool res = false; // no move → L
for (int i = 0; i < (int)a.size() && !res; i++)
for (ll p = 1; p <= a[i] && !res; p *= 2) {
vector<ll> b = a;
b[i] -= p; // take p coins from jar i
if (!win(b)) res = true;
}
return memo[a] = res;
}
int main() {
mt19937 rng(31);
for (int t = 1; t <= 500; t++) {
vector<ll> a(rng() % 4 + 1);
for (ll &x : a) x = rng() % 13;
ll x = 0;
for (ll v : a) x ^= v % 3;
if (win(a) != (x != 0)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
Output: all 500 tests passed.
Complexity vs the constraints
| Method | Time | Verdict |
|---|---|---|
| brute force over all tables | a1 · a2 · … · an states | TLE at 300 300 300 |
| Grundy table for one jar | 20 positions | a tool to find g(a) = a % 3 |
| XOR of ai % 3 | O(n) per test | instant |
Common mistakes (and the real outputs)
Bug 1: XOR the raw sizes
#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--) {
int n;
cin >> n;
ll x = 0; // XOR of the Grundy numbers
for (int i = 0; i < n; i++) {
ll a;
cin >> a;
x ^= a; // plain Nim?
}
cout << (x != 0 ? "Riya" : "Kabir") << "\n";
}
return 0;
}
Output on the sample: Kabir Riya Riya (expected Riya Kabir Riya). Plain XOR is only right for plain Nim (take any number). Here you must XOR the Grundy numbers.
Bug 2: mex as max + 1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N = 20;
vector<int> g(N + 1);
for (int i = 0; i <= N; i++) {
set<int> seen; // Grundy numbers of the options
for (int p = 1; p <= i; p *= 2) seen.insert(g[i - p]);
int mex = seen.empty() ? 0 : *seen.rbegin() + 1; // max + 1?
g[i] = mex;
}
for (int i = 0; i <= N; i++) cout << g[i] << " ";
return 0;
}
Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (expected 0 1 2 0 1 2 …). At 3 the options are {2, 1}: max + 1 = 3, but 0 is missing, so the mex is 0.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| count W games; odd → first wins | Kabir Kabir Kabir |
W/L throws away information | Grundy numbers |
x ^= a; |
Kabir Riya Riya |
that rule is only plain Nim | x ^= g(a) |
mex = max + 1 |
0 1 2 3 4 … |
mex is the smallest missing value | while (seen.count(m)) m++; |
| brute force on the whole table | Time Limit Exceeded | states multiply | one game at a time |
using a fixed-size bool seen[3] for mex |
wrong or out-of-bounds | Grundy values can grow | a set or a big enough array |
Mini project
Build a "Grundy lab": a function that takes a move rule (a lambda from a position to its list of options), computes Grundy numbers up to N, prints them, and detects a period. Use it for: Many Jars (powers of 2), take {1, 3, 4}, "split a pile into two unequal piles", and Nim itself. Then write a solver for sums of these games and stress test it against a brute force on tiny inputs.
Practice
-
Nim winning move. Print a plate and how many to take, or -1 if the position is losing. Plates
3 4 5?Answer
x = 3 ^ 4 ^ 5 = 2. The 3-plate has 3 ^ 2 = 1 < 3: take <b>2 from plate 1</b>. If x = 0 print -1. O(n). -
Many Jars with moves 1, 3 or 4. Grundy numbers and the winner for jars
2 5 7.Answer
Grundy table: 0 1 0 1 2 3 2, then it repeats with period 7: <b>g(a) = [0,1,0,1,2,3,2][a % 7]</b>. Jars 2, 5, 7: 0 ^ 3 ^ 0 = 3 ≠ 0 → <b>Riya</b>. -
Split a pile. A move splits one pile into two non-empty piles of different sizes; the player who can't move loses. Grundy numbers?
Answer
g(n) = mex{ g(a) ^ g(n − a) : 1 ≤ a < n − a }. Values for n = 0 … 20: <b>0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0</b> (no simple formula is known; precompute). -
Misère Nim. When does the first player win if the last laddoo loses?
Answer
If every plate has at most 1 laddoo: first wins when the number of 1-plates is <b>even</b>. Otherwise: first wins when the <b>XOR ≠ 0</b>, exactly like normal Nim (checked by brute force for 3 plates up to 4).
Quick quiz
Plain Nim with plates 2, 5, 7. Who wins?
A) First player · B) Second player · C) Depends on the first move · D) Draw
Answer
B. 010 ^ 101 ^ 111 = 000. XOR 0 is losing for the player to move, so the second player wins.
Interview questions
- State the winning condition for Nim. The player to move wins exactly when the XOR of the pile sizes is non-zero.
- What is mex? The smallest non-negative integer missing from a set.
- Define the Grundy number. The mex of the Grundy numbers of all positions reachable in one move; 0 for a terminal position.
- State the Sprague-Grundy theorem. Every impartial game under normal play is equivalent to a Nim pile of size equal to its Grundy number, and a sum of games has the XOR of the Grundy numbers.
- What is an impartial game? Both players have the same moves from every position (Nim, Many Jars); chess is not impartial.
- Why doesn't counting winning components work? W/L is only "Grundy zero or not"; XOR needs the actual values.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Sum of games | Several games side by side; each turn, move in one | the jars of Problem H |
| Nim | Take any number from one plate; last one wins | plates 3, 4, 5 |
XOR (^) |
Bitwise exclusive or: 1 where an odd number of bits are 1 | 3 ^ 4 ^ 5 = 2 |
| Bouton's theorem | Nim: L exactly when the XOR is 0 | 1 ^ 4 ^ 5 = 0 |
| mex | Smallest non-negative integer not in a set | mex{0, 1, 3} = 2 |
| Grundy number | mex of the options' Grundy numbers | g(3 coins) = 0 |
| Impartial game | Both players have the same moves | Nim |
| Sprague-Grundy theorem | Sum of games: XOR of Grundy numbers | x = Σ⊕ ai % 3 |
| Terminal position | No moves; Grundy 0 | empty table |
| Winning / losing position | Grundy ≠ 0 / Grundy = 0 | |
| Memoisation | Store each state's answer once | map<vector<ll>, bool> |
| Stress test | Formula vs brute force on random small cases | all 500 tests passed |
Summary
- W/L labels don't add up across games: counting W jars prints
Kabir Kabir Kabir. - Nim: the player to move loses exactly when the XOR of the plates is 0; the winning move shrinks a plate p to p ^ x.
- mex + Grundy numbers turn any impartial game into a Nim plate; Sprague-Grundy: XOR the Grundy numbers.
- Many Jars: g(a) = a % 3 (found with a printed table, then proved), answer = XOR of ai % 3, O(n).
- Real bugs: raw XOR (
Kabir Riya Riya), mex as max + 1 (0 1 2 3 4 …).
Solutions in C++, Java and Python
Problem H · Many Jars
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));
StringBuilder all = new StringBuilder();
String line;
while ((line = br.readLine()) != null) all.append(line).append(' ');
StringTokenizer in = new StringTokenizer(all.toString());
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(in.nextToken());
while (t-- > 0) {
int n = Integer.parseInt(in.nextToken());
long x = 0;
for (int i = 0; i < n; i++) x ^= Long.parseLong(in.nextToken()) % 3;
sb.append(x != 0 ? "Riya" : "Kabir").append('\n');
}
System.out.print(sb);
}
}
Python:
import sys
data = sys.stdin.buffer.read().split()
t = int(data[0]); pos = 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
x = 0
for i in range(n):
x ^= int(data[pos + i]) % 3
pos += n
out.append("Riya" if x else "Kabir")
print("\n".join(out))