~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Games (winning positions, Nim)
Win/lose states by DP, Nim sums and Grundy values.
Notes
Recognise it when: two players alternate, both play perfectly, and you're asked who wins (or how many winning first moves there are).
# a position is winning iff some move reaches a losing position
win = [False] * (n + 1)
for x in range(1, n + 1):
win[x] = any(not win[x - m] for m in moves if m <= x)
- Nim: the first player wins iff the xor of the pile sizes is non-zero.
- Sum of games: each part's Grundy value (mex of the values it can move to); xor them.
Gotchas: check who moves first and what happens at a position with no moves (usually: the player to move loses).
0 problems
No problems match those filters.