Games & Miscellaneous
Game theory, cycle detection and other classic tricks that do not fit elsewhere.
13 articles~89 min total
0/13
Sequences
- Range Minimum Query: Choosing a StructureA tour of the ways to answer 'minimum of A[L..R]': sqrt-decomposition, segment tree, Fenwick tree, sparse table, an offline DSU trick and the Cartesian tree, with Python code and trade-offs.9 minIntermediate
- K-th Order Statistic in O(N): QuickselectFind the k-th smallest element without sorting: partition around a random pivot and keep only the side that contains the answer, in expected O(N); with the deterministic median-of-medians variant.5 minIntermediate
- MEX (Minimal Excluded) of a SequenceFind the smallest non-negative integer missing from an array in O(N), and maintain it under point updates with counts and a heap of missing values.5 minIntermediate
- Maximum Subarray Sum and Related ProblemsFind the contiguous block with the largest sum by prefix-minimum or Kadane's algorithm in O(n), then extend it: length constraints, the maximum submatrix, and the maximum average by binary search.7 minIntermediate
Game theory
- Sprague-Grundy Theorem and NimSolve impartial two-player games by reducing each position to a Nim pile through its Grundy number, and combine independent games with XOR.9 minAdvanced
- Games on Arbitrary GraphsSolve a two-player game on a directed graph with cycles for every starting vertex at once in O(m): win, lose or draw by retrograde analysis from the terminal positions.12 minAdvanced
Scheduling
- Scheduling Jobs on One MachineOrder jobs on a single machine to minimize the total waiting penalty; the permutation (adjacent swap) method gives a sorting solution for linear, exponential and identical penalty functions.5 minIntermediate
- Scheduling Jobs on Two Machines: Johnson's RuleEvery job goes through machine 1 and then machine 2; Johnson's rule orders the jobs by a simple sorting rule to minimize the total completion time.3 minIntermediate
- Scheduling with Deadlines and DurationsComplete as many jobs as possible before their deadlines: go through the deadlines backwards, filling each time gap with the shortest remaining jobs, in O(n log n).5 minIntermediate
Classic problems
- The Josephus ProblemPeople stand in a circle and every k-th one is eliminated; find the survivor with a recurrence in O(n), the closed form for k = 2, and an O(k log n) method.5 minIntermediate
- Floyd's Cycle Detection (Tortoise and Hare)Detect a cycle in a linked list or any iterated function with O(1) memory, and find where it starts and how long it is.7 minIntermediate
- The 15 Puzzle: When Is It Solvable?A position of the sliding-tile puzzle is solvable exactly when the inversions of the tiles plus the row of the empty cell have the right parity; verified by exhaustive search on smaller boards.5 minIntermediate
- The Stern-Brocot Tree and Farey SequencesThe tree of all positive fractions built by mediants, its logarithmic search via continued fractions, and the Farey sequences obtained by trimming it.12 minAdvanced