Concepts52
Divide and Conquer DP Optimization
Divide and Conquer DP optimization speeds up DP transitions of the form dp[i][j] = min over k of dp[i-1][k] + C(k, j) when the optimal k is monotone in j.
Convex Hull Trick - Dynamic (LineContainer)
Dynamic Convex Hull Trick (LineContainer) maintains the lower or upper envelope of lines y = m x + b with O(log n) insertion and O(log n) query for arbitrary insertion order.
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.
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.
General Matching - Blossom Algorithm
Edmonds' Blossom Algorithm finds a maximum matching in any undirected graph, not just bipartite ones.
Biconnected Components
A biconnected component (block) is a maximal subgraph where removing any single vertex keeps it connected.
Virtual Tree (Auxiliary Tree)
A Virtual Tree (Auxiliary Tree) compresses a large tree into a much smaller tree that contains only the k important nodes and the LCAs needed to keep them connected.
Johnson's Algorithm
Johnson's Algorithm computes all-pairs shortest paths on sparse graphs by first removing negative edges via reweighting, then running Dijkstra from every vertex.
Aho-Corasick - DP Applications
Aho–Corasick (AC) turns a set of forbidden patterns into a finite automaton that lets you process or generate strings while tracking whether any pattern appears.
Palindromic Tree (Eertree)
A Palindromic Tree (Eertree) stores every distinct palindromic substring of a string as a node and can be built online in linear time.