Home — CP Notebook

Contest

template25 lines
.bashrc3 lines
.vimrc6 lines
hash3 lines
troubleshoot52 lines

Data structures

OrderStatisticTree— A set (not multiset!) with support for finding the n'th element, and finding the index of an element.17 lines
HashMap— Hash map with mostly the same API as unordered_map, but ~ 3x faster.8 lines
SegmentTree— Zero-indexed max-tree.19 lines
LazySegmentTree— Segment tree with ability to add or set values of large intervals, and compute max of intervals.50 lines
UnionFindRollback— Disjoint-set data structure with undo.21 lines
SubMatrix— Calculate submatrix sums quickly, given upper-left and lower-right corners (half-open).13 lines
Matrix— Basic operations on square matrices.26 lines
LineContainer— Container where you can add lines of the form kx+m, and query maximum values at points x.30 lines
Treap— A short self-balancing tree.53 lines
FenwickTree— Computes partial sums a[0] + a[1] + ..22 lines
FenwickTree2d— Computes sums a[i,j] for all i<I, j<J, and increases single elements a[i,j].22 lines
RMQ— Range Minimum Queries on an array.16 lines
MoQueries— Answer interval or tree path queries by finding an approximate TSP through the queries, and moving from one query to the next by adding/removing points at the ends.49 lines
Trie— Trie, support min and max XOR queries.51 lines
XorBasis— XOR Basis, support various XOR queries.46 lines
PersSegmentTree— Adds a time dimension to the segment tree.38 lines

Numerical

Polynomial17 lines
PolyRoots— Finds the real roots to a polynomial.23 lines
PolyInterpolate— Given n points (x[i], y[i]), computes an n-1-degree polynomial p that passes through them: p(x) = a[0]*x^0 + ..13 lines
BerlekampMassey— Recovers any n-order linear recurrence relation from the first 2n terms of the recurrence.20 lines
LinearRecurrence— Generates the k'th term of an n-order linear recurrence S[i] = Σ_j S[i-j-1]tr[j], given S[0 … ≥ n-1] and tr[0 … n-1].26 lines
GoldenSectionSearch— Finds the argument minimizing the function f in the interval [a,b] assuming f is unimodal on the interval, i.e.14 lines
HillClimbing— Poor man's optimization for unimodal functions.14 lines
Integrate— Simple integration of a function over an interval using Simpson's rule.7 lines
IntegrateAdaptive— Fast integration using an adaptive Simpson's rule.15 lines
Simplex— Solves a general linear maximization problem: maximize c^T x subject to Ax ≤ b, x ≥ 0.68 lines
Determinant— Calculates determinant of a matrix.15 lines
IntDeterminant— Calculates determinant using modular arithmetics.18 lines
SolveLinear— Solves A * x = b.38 lines
SolveLinear2— To get all uniquely determined values of x back from SolveLinear, make the following changes:.7 lines
SolveLinearBinary— Solves Ax = b over mathbb F_2.34 lines
MatrixInverse— Invert matrix A.35 lines
Tridiagonal— x=tridiagonal(d,p,q,b) solves the equation system \[ ( cb_0 b_1 b_2 b_3 ⋮ b_n-1 ) = ( cccccc d_0 & p_0 & 0 & 0 & … & 0 q_0 & d_1 & p_1 & 0 & … & 0 0 & q_1 & d_2 & p_2 & … & 0 ⋮ & ⋮ & ddots & ddots & ddots & ⋮ 0 & 0 & … & q_n-3 & d_n-2 & p_n-2 0 & 0 & … & 0 & q_n-2 & d_n-1 ) ( cx_0 x_1 x_2 x_3 ⋮ x_n-1 ).26 lines
FastFourierTransform— fft(a) computes hat f(k) = Σ_x a[x] exp(2π i · k x / N) for all k.35 lines
FastFourierTransformMod— Higher precision FFT, can be used for convolutions modulo arbitrary integers as long as Nlog_2N· mod < 8.6 · 10^14 (in practice 10^16 or higher).22 lines
NumberTheoreticTransform— ntt(a) computes hat f(k) = Σ_x a[x] g^xk for all k, where g=root^(mod-1)/N.35 lines
FastSubsetTransform— Transform to a basis with fast convolutions of the form c[z] = Σnolimits_z = x oplus y a[x] · b[y], where oplus is one of AND, OR, XOR.16 lines

Number theory

ModularArithmetic— Operators for modular arithmetic.19 lines
ModInverse— Pre-computation of modular inverses.3 lines
ModPow8 lines
ModLog— Returns the smallest x > 0 s.t.11 lines
ModSum— Sums of mod'ed arithmetic progressions.16 lines
ModMulLL— Calculate a· bbmod c (or a^b bmod c) for 0 ≤ a, b ≤ c ≤ 7.2· 10^18.11 lines
ModSqrt— Tonelli-Shanks algorithm for modular square roots.24 lines
FastEratosthenes— Prime sieve for generating all primes smaller than LIM.20 lines
MillerRabin— Deterministic Miller-Rabin primality test.12 lines
Factor— Pollard-rho randomized factorization algorithm.18 lines
euclid— Finds two integers x and y, such that ax+by=gcd(a,b).5 lines
CRT— Chinese Remainder Theorem.7 lines
phiFunction— Euler's φ function is defined as φ(n):=# of positive integers ≤ n that are coprime with n.8 lines
ContinuedFractions— Given N and a real number x ≥ 0, finds the closest rational approximation p/q with p, q ≤ N.21 lines
FracBinarySearch— Given f and N, finds the smallest fraction p/q ∈ [0, 1] such that f(p/q) is true, and p, q ≤ N.25 lines

Combinatorial

IntPerm— Permutation -> integer conversion.6 lines
multinomial— Computes C(k_1 + … + k_n, k_1, k_2, …, k_n) = ((Σ k_i)!)/(k_1!k_2!...k_n!).5 lines

Graph

BellmanFord— Calculates shortest paths from s in a graph that might have negative edge weights.23 lines
FloydWarshall— Calculates all-pairs shortest path in a directed graph that might have negative edge weights.12 lines
TopoSort— Topological sorting.8 lines
PushRelabel— Push-relabel using the highest label selection rule and the gap heuristic.48 lines
MinCostMaxFlow— Min-cost max-flow.79 lines
EdmondsKarp— Flow algorithm with guaranteed complexity O(VE²).36 lines
MinCut— After running max-flow, the left side of a min-cut from s to t is given by all vertices reachable from s, only traversing edges with positive residual capacity.0 lines
GlobalMinCut— Find a global minimum cut in an undirected graph, as represented by an adjacency matrix.21 lines
GomoryHu— Given a list of edges representing an undirected flow graph, returns edges of the Gomory-Hu tree.13 lines
HopcroftKarp— Fast bipartite matching algorithm.20 lines
DFSMatching— Simple bipartite matching algorithm.22 lines
MinimumVertexCover— Finds a minimum vertex cover in a bipartite graph.20 lines
WeightedMatching— Given a weighted bipartite graph, matches every node on the left with a node on the right such that no nodes are in two matchings and the sum of the edge weights is minimal.24 lines
GeneralMatching— Matching for general graphs.40 lines
SCC— Finds strongly connected components in a directed graph.24 lines
BiconnectedComponents— Finds all biconnected components in an undirected graph, and runs a callback for the edges in each.32 lines
BridgeFinding— Find the bridges in a graph in linear time.38 lines
ArticulationFinding— Find the articulation points in a graph in linear time.37 lines
2sat— Calculates a valid assignment to boolean variables a, b, c,..56 lines
EulerWalk— Eulerian undirected/directed path/cycle algorithm.15 lines
EdgeColoring— Given a simple, undirected graph with max degree D, computes a (D + 1)-coloring of the edges such that no neighboring edges share a color.31 lines
MaximalCliques— Runs a callback for all maximal cliques in a graph (given as a symmetric bitset matrix; self-edges not allowed).12 lines
MaximumClique— Quickly finds a maximum clique of a graph (given as symmetric bitset matrix; self-edges not allowed).49 lines
MaximumIndependentSet— To obtain a maximum independent set of a graph, find a max clique of the complement.0 lines
BinaryLifting— Calculate power of two jumps in a tree, to support fast upward jumps and LCAs.25 lines
LCA— Data structure for computing lowest common ancestors in a tree (with 0 as root).21 lines
CompressTree— Given a rooted tree and a subset S of nodes, compute the minimal subtree that contains all the nodes by adding all (at most |S|-1) pairwise LCA's and compressing edges.21 lines
HLD— Decomposes a tree into vertex disjoint heavy paths and light edges such that the path from any leaf to the root contains at most log(n) light edges.46 lines
LinkCutTree— Represents a forest of unrooted trees.90 lines
DirectedMST— Finds a minimum spanning tree/arborescence of a directed graph, given a root node.60 lines

Geometry

Point— Class to handle points in the plane.28 lines
lineDistance— 75mm Returns the signed distance between point p and the line containing points a and b.4 lines
SegmentDistance— 75mm Returns the shortest distance between point p and the line segment from point s to e.6 lines
SegmentIntersection— 75mm If a unique intersection point between the line segments going from s1 to e1 and from s2 to e2 exists then it is returned.13 lines
lineIntersection— 75mm If a unique intersection point of the lines going through s1,e1 and s2,e2 exists \1, point\ is returned.8 lines
sideOf— Returns where p is as seen from s towards e.9 lines
OnSegment— Returns true iff p lies on the line segment from s to e.3 lines
linearTransformation— 75mm Apply the linear transformation (translation, rotation and scaling) which takes line p0-p1 to line q0-q1 to point r.5 lines
Angle— A class for ordering angles (as represented by int points and a number of rotations around the origin).35 lines
CircleIntersection— Computes the pair of points at which two circles intersect.11 lines
CircleTangents— Finds the external tangents of two circles, or internal if r2 is negated.13 lines
CirclePolygonIntersection— Returns the area of the intersection of a circle with a ccw polygon.19 lines
circumcircle— 75mm The circumcirle of a triangle is the circle intersecting all three vertices.9 lines
MinimumEnclosingCircle— Computes the minimum circle that encloses a set of points.17 lines
InsidePolygon— Returns true if p lies within the polygon.11 lines
PolygonArea— Returns twice the signed area of a polygon.6 lines
PolygonCenter— Returns the center of mass for a polygon.9 lines
PolygonCut— 75mm Returns a vector with the vertices of a polygon with everything to the left of the line going from s to e cut away.13 lines
ConvexHull— 75mm Returns a vector of the points of the convex hull in counter-clockwise order.13 lines
HullDiameter— Returns the two points with max distance on a convex hull (ccw, no duplicate/collinear points).12 lines
PointInsideHull— Determine whether a point t lies inside a convex hull (CCW order, with no collinear points).14 lines
LineHullIntersection— Line-convex polygon intersection.39 lines
ClosestPair— Finds the closest pair of points.17 lines
kdTree— KD-tree (2d, can be extended to 3d).63 lines
FastDelaunay— Fast Delaunay triangulation.88 lines
PolyhedronVolume— Magic formula for the volume of a polyhedron.6 lines
Point3D— Class to handle points in 3D space.31 lines
3dHull— Computes all faces of the 3-dimension hull of a point set.49 lines
sphericalDistance— Returns the shortest distance on the sphere with radius radius between the points with azimuthal angles (longitude) f1 (φ_1) and f2 (φ_2) from x axis and zenith angles (latitude) t1 (θ_1) and t2 (θ_2) from z axis (0 = north pole).8 lines

Strings

KMP— pi[x] computes the length of the longest prefix of s that ends at x, other than s[0...x] itself (abacaba -> 0010123).16 lines
Zfunc— z[i] computes the length of the longest common prefix of s[i:] and s, except z[0] = 0.12 lines
Manacher— For each position in a string, computes p[0][i] = half length of longest even palindrome around pos i, p[1][i] = longest odd (half rounded down).13 lines
MinRotation— Finds the lexicographically smallest rotation of a string.8 lines
SuffixArray— Builds suffix array for a string.22 lines
SuffixTree— Ukkonen's algorithm for online suffix tree construction.50 lines
Hashing— Self-explanatory methods for string hashing.44 lines
AhoCorasick— Aho-Corasick automaton, used for multiple pattern matching.66 lines

Various

IntervalContainer— Add and remove intervals from a set of disjoint intervals.23 lines
IntervalCover— Compute indices of smallest set of intervals covering another interval.19 lines
ConstantIntervals— Split a monotone function on [from, to) into a minimal set of half-open intervals on which it has the same value.19 lines
TernarySearch— Find the smallest i in [a,b] that maximizes f(i), assuming that f(a) < … < f(i) ≥ … ≥ f(b).11 lines
LIS— Compute indices for the longest increasing subsequence.17 lines
FastKnapsack— Given N non-negative integer weights w and a non-negative target t, computes the maximum S <= t such that S is the sum of some subset of the weights.16 lines
KnuthDP— When doing DP on intervals: a[i][j] = min_i < k < j(a[i][k] + a[k][j]) + f(i, j), where the (minimal) optimal k increases with both i and j, one can solve intervals in increasing order of length, and search k = p[i][j] for a[i][j] only between p[i][j-1] and p[i+1][j].0 lines
DivideAndConquerDP— Given a[i] = min_lo(i) ≤ k < hi(i)(f(i, k)) where the (minimal) optimal k increases with i, computes a[i] for i = L..R-1.18 lines
FastMod— Compute a % b about 5 times faster than usual, where b is constant but not known at compile time.8 lines
FastInput— Read an integer from stdin.17 lines
BumpAllocator— When you need to dynamically allocate many objects and don't care about freeing them.8 lines
SmallPtr— A 32-bit pointer that points into BumpAllocator memory.10 lines
BumpAllocatorSTL— BumpAllocator for STL containers.14 lines
SIMD— Cheat sheet of SSE/AVX intrinsics, for doing arithmetic on several numbers at once.44 lines

Techniques

techniques159 lines

Competitive Programming Notebook

Contest

Data structures

Numerical

Number theory

Combinatorial

Graph

Geometry

Strings

Various

Techniques