Concepts113
Category
Convex Hull Trick (CHT)
The Convex Hull Trick (CHT) speeds up dynamic programs where each state is a minimum over linear functions, such as dp[i] = min_j (dp[j] + b[j] × a[i]).
Knuth Optimization
Knuth Optimization speeds up a class of interval dynamic programming (DP) from O(n^3) to O(n^2) by exploiting the monotonicity of optimal split points.
Digit DP - Advanced States
Digit DP counts integers in a range by scanning digits from most significant to least while maintaining compact state information.
DP with Probability
DP with probability models how chance flows between states over time by repeatedly redistributing mass according to transition probabilities.
Sum over Subsets (SOS) DP
Sum over Subsets (SOS) DP lets you compute F[mask] = sum of A[submask] over all submasks in O(n 2^n) instead of O(3^n).
DP with Expected Value
Dynamic programming with expected value solves problems where each state transitions randomly and we seek the expected cost, time, or steps to reach a goal.
Game Theory - Advanced Games
Sprague–Grundy (SG) theory solves impartial, normal-play, terminating games by assigning each position a nonnegative integer called its Grundy value.
Berlekamp-Massey Algorithm
Berlekamp–Massey (BM) finds the shortest linear recurrence that exactly fits a given sequence over a field (e.g., modulo a prime).
Gaussian Elimination over GF(2)
Gaussian elimination over GF(2) is ordinary Gaussian elimination where addition and subtraction are XOR and multiplication is AND.
Linear Recurrence
A linear recurrence defines each term as a fixed linear combination of a small, fixed number of previous terms.
Block-Cut Tree
A Block-Cut Tree decomposes an undirected graph into biconnected components (blocks) and articulation points, forming a bipartite tree.
Hungarian Algorithm
The Hungarian algorithm solves the square assignment problem (matching n workers to n jobs) in O(n^{3}) time using a clever potential (label) function on vertices.