Concepts116
Category
DP on Broken Profile - Plug DP
Plug DP (DP on broken profile with plugs) sweeps a grid cell by cell while remembering how partial path segments cross the frontier as labeled “plugs.”
Matrix Exponentiation - Advanced
Matrix exponentiation turns repeated linear transitions into fast O(n^{3} log k) computation using exponentiation by squaring.
Voronoi Diagram and Delaunay
Voronoi diagrams partition the plane so each region contains points closest to one site, while the Delaunay triangulation connects sites whose Voronoi cells touch.
Sqrt Decomposition on Queries
Sqrt decomposition on queries (time blocking) processes Q operations in blocks of size about \(\sqrt{Q}\) to balance per-query overhead and rebuild cost.
Polynomial Operations
Fast polynomial operations treat coefficients like numbers but use FFT/NTT to multiply in O(n \log n) time instead of O(n^2).
Parallel Binary Search
Parallel Binary Search (PBS) lets you binary-search the answers of many queries at once by batching them by their current mid value.
Convolution Applications
Convolution turns local pairwise combinations (like matching characters or adding two dice) into a single fast transform–multiply–inverse pipeline.
NTT (Number Theoretic Transform)
The Number Theoretic Transform (NTT) is an FFT-like algorithm that performs discrete convolutions exactly using modular arithmetic instead of floating-point numbers.
Randomized Algorithms
Randomized algorithms use coin flips (random bits) to guide choices, often making code simpler and fast on average.
FFT (Fast Fourier Transform)
FFT converts a polynomial from coefficients to values at the n-th roots of unity in O(n log n) time, enabling fast multiplication via pointwise products.
CDQ Divide and Conquer
CDQ divide and conquer is an offline technique that splits the timeline (or one coordinate) and lets updates from the left half contribute to queries in the right half.
Matrix Exponentiation
Matrix exponentiation turns repeated linear transitions into a single fast power of a matrix using exponentiation by squaring.