Skip to content

Template Library

This page is the map for the repo's reusable contest-ready code. The actual implementations live under templates/, but the goal here is to keep you inside the repo's learn -> practice -> retrieve -> reuse loop for as long as possible before you jump from repo context into raw source.

Fast Pick By Signal

Retrieval Flow

Use the library in this order:

  1. identify the smallest valid pattern from the topic page or cheatsheet
  2. open the matching template and copy only the parts your problem really needs
  3. sanity-check the invariant and boundary policy before integrating it into the solution

If you are still unsure which family to use, start from the Notebook instead of browsing files blindly.

If the template is integrated but still feels untrustworthy, switch immediately to the Stress testing workflow instead of guessing at bugs.

If you are still stabilizing the local C++ loop itself, pair these first:

Exact Starter Routes

Use these route cards when you want stronger in-site context before touching raw template code.

Need Learn / check first Reuse Compare against
one exact pattern against one text KMP kmp.cpp String Matching
one static string, longest palindrome, or all center radii Palindromes / Manacher manacher.cpp Longest Palindrome
one growing lowercase string, distinct palindromes, or longest palindromic suffix Eertree / Palindromic Tree eertree.cpp Distinct Palindromic Substrings
one small regex language with (), |, *, ., and exact full-string membership Regular Expressions / Finite Automata regex-thompson-nfa.cpp Regex Membership
one optimal binary prefix-code tree from positive symbol frequencies Huffman / Data Compression huffman-coding.cpp Huffman Coding Benchmark
critical roads or cut vertices in one static undirected graph Bridges, Articulation Points, And Biconnected Components bridges-articulation-lowlink.cpp Necessary Roads
one static graph walk that must use every edge exactly once Eulerian Path / Cycle eulerian-path-cycle.cpp Mail Delivery
one binary order-n sequence that must contain every length-n bitstring exactly once De Bruijn Sequence de-bruijn-sequence-binary.cpp De Bruijn Sequence
one valid boolean assignment under binary clauses 2-SAT two-sat.cpp Giant Pizza
one rooted subtree sum with point updates Euler Tour / Subtree Queries euler-tour-subtree.cpp Subtree Queries
one marked-subset query on a static rooted tree after adding only the LCAs that still matter Virtual Tree / Auxiliary Tree virtual-tree.cpp Kingdom and its Cities
one convex polygon formed by summing two CCW convex polygons Minkowski Sum minkowski-sum-convex.cpp Mogohu-Rea Idol (stretch)
static tree, point updates, path maximum Heavy-Light Decomposition hld-path-max.cpp Path Queries II
centroid tree plus per-node centroid ancestors/distances Centroid Decomposition centroid-decomposition.cpp Ciel the Commander
dynamic forest with online link / cut, vertex adds, and path sums Link-Cut Tree link-cut-tree-path-sum.cpp Dynamic Tree Vertex Add Path Sum
dynamic forest with online link / cut, vertex adds, and subtree-side sums on one existing edge Euler Tour Tree euler-tour-tree-subtree-sum.cpp Dynamic Tree Vertex Add Subtree Sum
one undirected weighted graph with no designated source/sink, asking for the cheapest disconnection cut Randomized / Global Min-Cut stoer-wagner-global-mincut.cpp Minimum Cut
one undirected weighted graph needs many pairwise min-cuts compressed into one weighted cut tree Gomory-Hu Tree gomory-hu-tree.cpp MCQUERY
plain directed max flow where you want a preflow / height-label engine sibling instead of blocking-flow augmentation Maximum Flow push-relabel-max-flow.cpp Maximum Flow
connectivity under an offline add/remove edge timeline DSU Rollback / Offline Dynamic Connectivity dsu-rollback-dynamic-connectivity.cpp Dynamic Connectivity
one versioned array with point assignment and old-version range sums Persistent Data Structures persistent-segment-tree-point-set-sum.cpp Range Queries and Copies
one branching list/sequence where merge, head, or tail operations create new roots while old roots stay alive Persistent Treap persistent-treap-list-sum.cpp Persistent List
one mutable sequence with cut/paste or insert/erase by position Treap / Implicit Treap implicit-treap-sequence.cpp Cut and Paste
one static array with subarray k-th / count <= x / count == x queries Wavelet Tree wavelet-tree.cpp MKTHNUM - K-th Number
one static array with many range queries where add/remove at one endpoint is cheap Mo's Algorithm mos-algorithm.cpp Powerful Array
one live multiset of integers with insert / erase / maximum xor queries Binary Trie / XOR Queries binary-trie-xor.cpp Vasiliy's Multiset
one dynamic ordered set with online rank / k-th / count-smaller queries PBDS / Order Statistics Tree pbds-ordered-set.cpp ORDERSET - Order Statistic Set
one high-fanout textbook ordered dictionary where search + insert + split-full-child are the whole lesson B-Trees b-tree-insert-search.cpp B-Tree Dictionary
one probabilistic textbook ordered dictionary where forward-pointer towers and update[] splicing are the whole lesson Skip Lists skiplist-ordered-set.cpp Skiplist Dictionary
one bounded-universe integer set where predecessor / successor via prefix hashing is the whole lesson X-Fast / Y-Fast Tries x-fast-trie.cpp X-Fast Dictionary
one live set of half-open intervals with online insert / erase / any-overlap queries Interval Trees interval-tree-overlap-treap.cpp Reservation System
one self-adjusting ordered multiset where you explicitly want rotate / splay / parent machinery or a direct bridge into link-cut tree Splay Tree splay-tree-ordered-set.cpp Ordinary Balanced Tree
many singleton heaps that must meld online and answer delete-min by the heap containing x Pairing Heap / Leftist Heap leftist-heap-meldable-pq.cpp Mergeable Heap 1
one interval partition of constant values where range assign keeps collapsing runs and range walks are acceptable ODT / Chtholly odt-interval-set.cpp Willem, Chtholly and Seniorious
one first-smaller / first-greater boundary scan where each dominated element dies forever Monotonic Stack / Queue monotonic-stack-nearest-smaller.cpp Nearest Smaller Values
online add-line / query-min on arbitrary integer x without predeclaring the domain Convex Hull Trick / Li Chao Tree line-container.cpp Line Add Get Min
affine DP with online line insertion on one known integer x-domain Convex Hull Trick / Li Chao Tree li-chao-tree.cpp Monster Game II
subset-like exact search with n around 35 to 45 and a cheap merge over half summaries Meet-In-The-Middle meet-in-the-middle-subset-sum.cpp Meet in the Middle
one repeated buy-vs-rent decision where the future horizon is hidden and the whole lesson is the first competitive-ratio benchmark Online Algorithms ski-rental-threshold.cpp Ski Rental
one smooth differentiable loss where the whole lesson is fixed-step batch gradient descent on one affine predictor Gradient Descent gradient-descent-linear-regression-1d.cpp Linear Regression Gradient Descent Benchmark
one linearly separable binary classifier where updates happen only on mistakes and the exact lesson is the perceptron Machine Learning Algorithms perceptron-linear-separable.cpp Perceptron Classification Benchmark
one promise-problem simulator where a Boolean oracle is guaranteed constant or balanced and the whole lesson is the Deutsch-Jozsa amplitude test Quantum Algorithms deutsch-jozsa-simulator.cpp Deutsch-Jozsa Oracle Benchmark
one additive scan where the whole lesson is a Blelloch exclusive-scan tree plus work / span reasoning Parallel Algorithms blelloch-exclusive-scan.cpp Parallel Prefix Sum Benchmark
one small continuous LP already normalized to maximize c^T x, Ax <= b, x >= 0 Simplex simplex-max-ax-le-b.cpp Cheese, If You Please
one explicit ground set with two independence oracles and a maximum-cardinality common independent set Matroid Intersection matroid-intersection-oracle.cpp Pick Your Own Nim
merge one or many congruences into one residue modulo lcm Chinese Remainder / Linear Congruences chinese-remainder.cpp General Chinese Remainder
solve one modular exponent equation a^x ≡ b (mod m) with contest-sized square-root storage BSGS / Discrete Log discrete-log-bsgs.cpp Discrete Logarithm Mod
recover one modular square root x^2 ≡ a (mod p) under one prime modulus Modular Square Root / Discrete Root mod-sqrt-tonelli-shanks.cpp Sqrt Mod
find one primitive root modulo one prime once factoring p-1 is already under control Primitive Root primitive-root-prime.cpp Primitive Root
factor one 64-bit integer into sorted prime factors Pollard-Rho pollard-rho-factorize.cpp Factorize
solve one linear system Ax = b modulo one prime and recover any valid assignment Gaussian Elimination / Linear Algebra gaussian-elimination-mod-prime.cpp System of Linear Equations
large nCk mod p with one small prime modulus Lucas Theorem / Large Binomial Mod Prime lucas-binomial.cpp Binomial Coefficient (Prime Mod)
gcd-1 pair counts or divisor-side inclusion-exclusion over bounded values Mobius And Multiplicative Counting mobius-linear-sieve.cpp Counting Coprime Pairs
one summatory divisor-function prefix sum where sigma = 1 * id opens the route and equal floor(n / d) quotients can be grouped Dirichlet Convolution / Prefix Sums Of Number-Theoretic Functions dirichlet-convolution-sigma-sum.cpp Sum of Divisors
one huge prefix sum of phi or mu where the recurrence lives on the quotient set Q_n Min_25 / Du Jiao du-jiao-prefix-phi-mu.cpp Sum of Totient Function
one fixed-order linear recurrence or repeated linear transition under modulo Linear Recurrence / Matrix Exponentiation matrix-exponentiation.cpp Throwing Dice
one known linear recurrence of moderate order with one huge k, or enough prefix terms to recover that recurrence first Berlekamp-Massey / Kitamasa berlekamp-massey-kitamasa.cpp K-th Term of Linearly Recurrent Sequence
subset xor span, representability, or maximum subset xor from any subset of inserted numbers XOR Basis / Linear Basis xor-basis.cpp XMAX - XOR Maximization
impartial normal-play heaps/components under one fixed move set, combined by xor of Grundy values Game Theory / Sprague-Grundy sprague-grundy-subtract-set.cpp S-Nim
repeated discrete random steps with bounded sum/state and one exact probability/expectation from the final PMF Probability probability-distribution-dp.cpp Dice Probability
exact convolution modulo 998244353 FFT / NTT ntt.cpp Convolution
point updates plus range sums on an array Segment Tree segment-tree-iterative.cpp Dynamic Range Sum Queries
online range add plus range sum on an array Lazy Segment Tree segment-tree-lazy-range-add-sum.cpp HORRIBLE
online range chmin / chmax / add / sum on one array Segment Tree Beats segment-tree-beats.cpp Range Chmin Chmax Add Range Sum
one inverse under composite modulus or ax + by = c Modular Arithmetic extended-gcd-diophantine.cpp Euclid Problem

Template Card Contract

For mature templates, this repo uses six short metadata fields:

  • Signal: the fastest cue that this template is the right family
  • Assumes: the boundary meaning, invariant, or data-shape contract already baked in
  • Exposes: the function, struct, or return contract you are expected to reuse
  • Complexity: the standard operation cost you should keep in your head while using it
  • Main trap: the bug most likely to survive hand tests
  • Links: the strongest reopening path when trust is low

The library page carries fuller cards for the pilot family and chooser tables for the rest. The template file itself only keeps the compact version.

Foundations Pilot Cards

contest-main.cpp

  • Signal: start a normal single-file batch solution with the smallest clean skeleton
  • Assumes: standard C++ streams, one-file submission, logic still needs to be written from scratch
  • Exposes: one minimal main() with fast iostream setup already in place
  • Complexity: no algorithmic cost; this is a starter scaffold
  • Main trap: copying the skeleton and then letting local debug prints leak into judged output
  • Links: C++ Language For Contests, Foundations Cheatsheet, Weird Algorithm

fast-io.cpp

  • Signal: large ordinary stdin/stdout input, but still no interactive or custom-judge behavior
  • Assumes: C++ streams only; no casual mixing with scanf / printf after disabling sync
  • Exposes: one reusable init_fast_io() helper plus a minimal main()
  • Complexity: same asymptotic complexity as ordinary iostream code; this is about constant-factor stream setup
  • Main trap: mixing unsynchronized iostreams with C stdio and then debugging ghosts that are really I/O policy bugs
  • Links: C++ Language For Contests, Foundations Cheatsheet

sort-and-comparator.cpp

  • Signal: records need to be ordered by one main key plus an explicit tie rule
  • Assumes: the comparator is a strict weak ordering and the tie behavior matters enough to spell out
  • Exposes: one record struct plus one lambda comparator pattern
  • Complexity: O(n log n) sorting plus linear scan after sorting in the common use case
  • Main trap: incomplete or inconsistent comparator logic that makes the proof and the implementation quietly disagree
  • Links: Sorting, Ferris Wheel, Movie Festival

prefix-sum-1d.cpp

  • Signal: many static range sums or counts, no updates
  • Assumes: one stable indexing convention and pref[0] = 0
  • Exposes: a PrefixSum1D struct with sum(l, r) over a half-open-style internal prefix layout
  • Complexity: O(n) preprocessing, O(1) per query
  • Main trap: mixing inclusive and half-open interval formulas in the same solution
  • Links: Prefix Sums, Static Range Sum Queries

binary-search-first-true.cpp

  • Signal: monotone predicate, want the first feasible answer
  • Assumes: l is bad, r is good, and the answer stays in (l, r]
  • Exposes: a first_true(l, r, is_good) helper that returns the first good integer
  • Complexity: O(log range) predicate calls
  • Main trap: writing a check that is not really monotone, or forgetting what l and r mean after two iterations
  • Links: Binary Search, Factory Machines, Foundations Cheatsheet

Foundations Chooser

Template Signal Avoid when Teaching anchor Representative use
contest-main.cpp start a clean single-file batch solution you already need a protocol harness or a real reusable data structure C++ Language Weird Algorithm
fast-io.cpp large ordinary stdin/stdout input interactive tasks or mixed stdio policy C++ Language Missing Number
sort-and-comparator.cpp sort records by one main key plus ties the proof does not depend on sorted order yet Sorting Movie Festival
binary-search-first-true.cpp monotone predicate, first feasible answer the predicate is not monotone Binary Search Factory Machines
binary-search-last-false.cpp monotone predicate, want the last bad point you are really reasoning in first-true semantics Binary Search Factory Machines
prefix-sum-1d.cpp many static range sums or counts updates happen between queries Prefix Sums Static Range Sum Queries
difference-array.cpp many offline range additions, final reconstruction only online queries or updates interleave with answers Difference Arrays Range Update Queries
two-pointers-variable-window.cpp monotone sliding window with forward-only boundaries negative values or non-monotone validity break the window logic Two Pointers TFIELD

Data Structures Chooser

Template Signal Avoid when Teaching anchor Representative use
dsu-basic.cpp merge-only connectivity or component tracking deletions, rollback, parity constraints, or path aggregates DSU C11XU
dsu-rollback-dynamic-connectivity.cpp connectivity or component count under an offline add/remove edge timeline the problem is truly online, or one monotone sweep already removes the need for rollback DSU Rollback / Offline Dynamic Connectivity Dynamic Connectivity
small-to-large-subtree-merge.cpp every node needs one subtree answer and each child contributes a mergeable container such as a frequency map or set one fixed-size tree DP state already works, Euler-tour intervals plus another structure close the problem cleanly, or one active add/remove range is the real invariant DSU On Tree / Small-To-Large Distinct Colors
persistent-segment-tree-point-set-sum.cpp branching versions with point assignment and range sums over old snapshots range updates dominate, only one current state matters, or the aggregate is not the ordinary segment-tree one Persistent Data Structures Range Queries and Copies
persistent-treap-list-sum.cpp branching list roots where split/merge sequence surgery must stay persistent across old versions the structure is a fixed array, only one current sequence matters, or key-based ordered-set queries are the real job Persistent Treap Persistent List
treap-key-ordered-set.cpp one self-hosted ordered set needs split/merge by key, online rank, or k-th queries without relying on GNU PBDS plain predecessor/successor is enough, GNU PBDS is already the simpler exact route, or sequence surgery by position is the real job Treap / Implicit Treap Salary Queries
implicit-treap-sequence.cpp one mutable sequence where split/merge by position is the cleanest way to express cut/paste or insert/erase edits fixed-length interval updates already fit segment trees, or ordered-set predecessor/successor is the only need Treap / Implicit Treap Cut and Paste
wavelet-tree.cpp one static array with subarray order statistics or value-threshold counts where the query descends by value partitions updates happen, one active current range is the real invariant, or version roots / prefix trees are the intended story Wavelet Tree MKTHNUM - K-th Number
mos-algorithm.cpp one static array where the exact current-range answer can be maintained by endpoint add/remove updates a monotone sweep already works, updates happen between queries, or the problem is still in tree/time-reduction territory Mo's Algorithm Powerful Array
binary-trie-xor.cpp one live multiset of non-negative integers where xor optimization against one stored element is the whole query the task is subset xor, plain ordered-set logic, or a richer counting-trie variant than this starter advertises Binary Trie / XOR Queries Vasiliy's Multiset
pbds-ordered-set.cpp one dynamic ordered set needs online rank, k-th, or count-smaller queries, with an optional pair-key wrapper if duplicates matter predecessor / successor is enough, compressed prefix counts make Fenwick simpler, or split/merge by key is the real route PBDS / Order Statistics Tree ORDERSET - Order Statistic Set
b-tree-insert-search.cpp one high-fanout multiway ordered dictionary where search and insert are taught through root split and split-full-child ordinary contest ordered-set work already fits PBDS or set, split/merge is the real primitive, or the lesson is overlap/segment aggregation rather than fanout B-Trees B-Tree Dictionary
skiplist-ordered-set.cpp one probabilistic ordered dictionary where tower search plus update[] splicing is the real structural lesson rank / k-th or split/merge is the actual invariant, or you only need one ordinary ordered set under contest pressure Skip Lists Skiplist Dictionary
x-fast-trie.cpp one bounded non-negative integer set where predecessor / successor through prefix hashing and leaf links is the actual invariant the keys are not from one fixed-width universe, xor optimization is the real query, or PBDS already closes the contest job more simply X-Fast / Y-Fast Tries X-Fast Dictionary
interval-tree-overlap-treap.cpp one live set of half-open intervals needs online overlap checks, and subtree max_r is the real pruning invariant intervals stay pairwise disjoint so a simple ordered-set neighbor check is enough, queries are offline, or the task is aggregate coverage on a fixed coordinate universe Interval Trees Reservation System
splay-tree-ordered-set.cpp one self-adjusting ordered multiset needs rank / k-th plus direct rotate / splay / parent practice, or you want the cleanest exact bridge into link-cut tree GNU PBDS already solves the interface, split/merge is the real primitive, or dynamic-forest path logic is already the actual task Splay Tree Ordinary Balanced Tree
leftist-heap-meldable-pq.cpp many singleton heaps keep merging and queries ask for the minimum of the heap containing x ordinary priority_queue is enough, predecessor / rank logic is the real need, or split/merge ordered sets are the true abstraction Pairing Heap / Leftist Heap Mergeable Heap 1
odt-interval-set.cpp piecewise-constant interval partitions where assign keeps collapsing runs and the answer is computed by walking the current touched segments the task needs hard worst-case range guarantees, there is no interval-collapsing operation, or lazy / beats segment trees already close the range algebra cleanly ODT / Chtholly Willem, Chtholly and Seniorious
line-container.cpp online add-line / query-min with full-domain lines and arbitrary integer x queries, without declaring the domain first query x-domain is already known and bounded enough for Li Chao, lines are only active on x-subsegments, or monotone hull is enough Convex Hull Trick / Li Chao Tree Line Add Get Min
fenwick-point-prefix.cpp point updates plus prefix or range sums range assignment, min/max merges, or mixed lazy operations Fenwick Tree CVP00001
segment-tree-iterative.cpp point updates with range sums on a mutable array you need a generic monoid, lazy propagation, or a fully static structure Segment Tree Dynamic Range Sum Queries
segment-tree-lazy-range-add-sum.cpp online range add plus range sum on a mutable array range-assign tags, affine updates, or problems that are really offline difference-array tasks Lazy Segment Tree HORRIBLE
segment-tree-beats.cpp online range chmin / chmax / add / sum where clamp updates depend on current extrema distribution a plain lazy-tag algebra already works, or the task is only one narrower beats-like modulo/historic variant than this starter advertises Segment Tree Beats Range Chmin Chmax Add Range Sum
sparse-table-rmq.cpp static range minimum query online updates or any non-RMQ aggregate Sparse Table Static Range Minimum Queries
heap-lazy-delete.cpp min-heap behavior with delayed deletions by value predecessor/order-statistics queries or deletes that do not correspond to live values Heaps And Ordered Sets Heaps And Ordered Sets Ladder
multiset-predecessor.cpp predecessor or floor queries with duplicates you need rank / order statistics or heap-only behavior Heaps And Ordered Sets Concert Tickets
sliding-median-two-multisets.cpp maintain a lower median under insert/erase with duplicates you need arbitrary quantiles or a different median convention Heaps And Ordered Sets Heaps And Ordered Sets Ladder
monotonic-stack-nearest-smaller.cpp first smaller / greater boundary in one linear scan where dominated candidates never return the active set is not monotone, or you really need a window-extrema deque instead of one-sided boundaries Monotonic Stack / Queue Nearest Smaller Values
monotonic-deque-min.cpp sliding minimum or DP over a moving interval the valid set is not a forward-only window Monotonic Stack / Queue Sliding Window Minimum
offline-query-skeleton.cpp sort events and queries by one monotone key, then sweep once answers depend on previous answers or truly online updates Offline Tricks Distinct Values Queries

Graphs Chooser

Template Signal Avoid when Teaching anchor Representative use
bfs.cpp unweighted shortest path or layer exploration weighted edges matter BFS And DFS Message Route
dfs-iterative.cpp traversal/components without recursion risk layer distance is the proof-critical object BFS And DFS Counting Rooms
zero-one-bfs.cpp shortest paths with edge weights only 0/1 arbitrary nonnegative weights Shortest Paths Shortest Paths Ladder
dijkstra.cpp nonnegative weighted shortest paths any reachable negative edge survives after modeling Shortest Paths QOS
bellman-ford.cpp negative edges or reachable negative-cycle detection all weights are nonnegative and sparse enough for Dijkstra Shortest Paths Shortest Paths Ladder
floyd-warshall.cpp all-pairs shortest paths on small n sparse large graphs or one-source queries only Shortest Paths Shortest Paths Ladder
kruskal.cpp MST from an edge list directed reachability or path-distance questions MST Road Reparation
toposort-kahn.cpp explicit DAG ordering from indegrees you need SCC condensation or cyclic-component structure, not just cycle detection Topological Sort And SCC Course Schedule
scc-kosaraju.cpp compress directed cycles into SCC ids the graph is undirected or plain topo order already exists Topological Sort And SCC SCC / Toposort Ladder
bridges-articulation-lowlink.cpp undirected graph with critical edges, critical vertices, or low-link preprocessing before deeper BCC work the graph is directed, dynamic, or already a tree Bridges, Articulation Points, And Biconnected Components Necessary Roads
eulerian-path-cycle.cpp one static graph walk or ordering that must use every edge exactly once, in either the undirected or directed setting the task is subtree flattening, shortest path, or online graph updates rather than all-edge traversal Eulerian Path / Cycle Mail Delivery
de-bruijn-sequence-binary.cpp one binary order-n string that must contain every length-n bitstring exactly once as a substring the graph is already explicit, the overlap model is irregular, or the task is plain path finding instead of window-coverage construction De Bruijn Sequence De Bruijn Sequence
two-sat.cpp boolean variables with binary clauses and one witness assignment clauses are not binary, variables are not boolean, or optimization dominates the task 2-SAT Giant Pizza
tree-isomorphism-rooted.cpp two rooted trees must be compared up to child permutation, or an unrooted comparison reduces to trying one or two centers first the task is about values on the tree, labels matter, or path/subtree queries are the real bottleneck Tree Isomorphism Tree Isomorphism I
euler-tour-subtree.cpp one rooted subtree interval with point updates and subtree sums arbitrary path queries, dynamic tree changes, or child-merge DP are the real bottleneck Euler Tour / Subtree Queries Subtree Queries
lca-binary-lifting.cpp many static ancestor or LCA queries on one rooted tree dynamic trees or path aggregates are the real bottleneck LCA Company Queries II
virtual-tree.cpp one static rooted tree where each query marks only a small subset and you must DP/count on the compressed union of their paths whole-tree DP, ordinary subtree flattening, or online path aggregates are the real bottlenecks Virtual Tree / Auxiliary Tree Kingdom and its Cities
hld-path-max.cpp static tree with node updates and path maximum queries edge-valued paths, lazy range updates, or non-commutative path aggregates Heavy-Light Decomposition Path Queries II
centroid-decomposition.cpp static tree problems that need a centroid tree, balanced recursive splits, or one O(log n) centroid-ancestor chain per node subtree-only flattening, HLD-style path aggregates, or dynamic tree changes are the real fit Centroid Decomposition Ciel the Commander
link-cut-tree-path-sum.cpp dynamic forest with online link / cut, vertex adds, and path-sum queries the tree is static, only subtree queries matter, or the task is offline connectivity rather than online dynamic paths Link-Cut Tree Dynamic Tree Vertex Add Path Sum
euler-tour-tree-subtree-sum.cpp dynamic forest with online link / cut, vertex adds, and subtree-side sums on one existing edge the tree is static, the live query is really one path aggregate, or you only need offline connectivity Euler Tour Tree Dynamic Tree Vertex Add Subtree Sum
stoer-wagner-global-mincut.cpp one undirected weighted graph has no designated s-t, and the answer is the cheapest cut that disconnects the graph at all the graph is directed, one particular s-t pair matters, or the real task is many pairwise min-cuts Randomized / Global Min-Cut Minimum Cut
gomory-hu-tree.cpp one undirected weighted graph needs many pairwise min-cuts or one tree-compressed cut family the graph is directed, only one cut is needed, or the hard part is already lower bounds / min-cost transport instead Gomory-Hu Tree MCQUERY
dinic.cpp max-flow / min-cut on a moderate network edge costs matter or pure bipartite matching is the only goal Maximum Flow Police Chase
push-relabel-max-flow.cpp plain static max-flow / min-cut where you want a height-label preflow engine or a denser hard-benchmark sibling costs or lower bounds change the model, or the task is no longer one ordinary directed s-t flow Maximum Flow Maximum Flow
flow-lower-bounds.cpp feasible circulation where every directed edge has lower <= flow <= upper, or one lower-bounded s-t model after adding t -> s costs dominate, the task is still plain max flow, or you forgot to close the s-t model into a circulation Flow With Lower Bounds Reactor Cooling
min-cost-flow.cpp flow value and edge costs both matter, with nonnegative initial residual costs in this snippet max-flow value alone is enough or negative-cost edges need an initial potential pass Maximum Flow MINCOST
hopcroft-karp.cpp bipartite maximum matching at scale matching is not bipartite or costs/weights matter Matching School Dance
gale-shapley-stable-marriage.cpp two equal-sized sides with complete strict preference lists and a stability objective the real objective is maximum pairs, minimum total cost, or richer quota / tie variants Stable Marriage Stable Marriage
hungarian-assignment.cpp dense square weighted assignment where every row and every column must be used exactly once the task is only cardinality matching, capacities dominate, or sparse costed transport is the clearer first model Hungarian / Assignment Problem Task Assignment
edmonds-blossom.cpp undirected maximum matching where the graph is not guaranteed bipartite the graph is still bipartite, weighted assignment is the true model, or weighted blossom is required Edmonds Blossom / General Matching General Matching

Strings Chooser

Template Signal Avoid when Teaching anchor Representative use
rolling-hash.cpp same-length substring fingerprints, borders, or LCP via binary search exact proof-critical matching needs zero collision risk by itself String Hashing Finding Borders
kmp.cpp one exact pattern against one text, plus border-chain reuse many patterns or all-substring aggregation KMP String Matching
z-function.cpp one-string diagnostics, prefix matches, borders, or periods dictionary matching over many patterns Z-Function Finding Periods
manacher.cpp one static string where longest palindrome or all odd/even center radii matter dynamic updates or many arbitrary palindrome queries are the real task Palindromes / Manacher Longest Palindrome
eertree.cpp one growing lowercase string where distinct palindromes or longest palindromic suffixes matter the string is static and Manacher already solves it, or the task is arbitrary substring palindrome checks Eertree / Palindromic Tree Distinct Palindromic Substrings
trie-basic.cpp many words with shared-prefix transitions a sort/lower_bound pass already solves the task Trie Word Combinations
aho-corasick.cpp many patterns against one text only one pattern matters or you need all substrings of one base string instead Aho-Corasick Finding Patterns
regex-thompson-nfa.cpp one small regex language with (), |, *, ., and exact full-string membership the task is one literal pattern, many literal patterns, or industrial regex semantics with features beyond the starter contract Regular Expressions / Finite Automata Regex Membership
suffix-tree.cpp one static lowercase text should behave like a compressed substring index for existence or earliest-occurrence queries suffix order is the real object, many patterns are better handled by a pattern trie, or the string grows online Suffix Tree Pattern Positions
suffix-array.cpp global suffix order, LCP, repeated substring queries online extension or state-based substring aggregation is the core need Suffix Array And LCP Repeating Substring
suffix-automaton.cpp one base string, all substrings matter, and state aggregation helps many independent patterns are matched against one long text Suffix Automaton Distinct Substrings
huffman-coding.cpp one optimal binary prefix-code tree or one repeated merge-two-smallest objective the task is a feasibility scan, one industrial compression format, or only raw priority-queue mechanics Huffman / Data Compression Huffman Coding Benchmark

Current Templates

Foundations

  • chooser table above; use the pilot cards plus the foundations chooser before browsing raw files

Data Structures

  • chooser table above; this group now carries the same compact contract style as foundations

Graphs

  • chooser table above; use it before browsing raw graph templates under contest pressure

Dynamic Programming

Dynamic Programming Chooser

Template Signal Avoid when Teaching anchor Representative use
knapsack-01.cpp 0/1 item choices with one capacity axis items are unbounded or the state is not a capacity DP Knapsack Family Book Shop
bitmask-subset-iterate.cpp forward subset DP that adds one missing bit at a time n is too large for 2^n, or transitions need arbitrary submasks instead of one added bit Bitmask DP VMMARBLE
sos-dp-zeta.cpp one full mask cube where each mask needs all-submask or all-superset aggregates, or one witness carried through the same sweep the state evolves by adding one bit, the mask is a grid frontier, or the real transform is beyond subset/superset zeta sweeps SOS DP Compatible Numbers
fwht-xor-convolution.cpp two full mask functions combine under xor, or the real family is boolean-cube transforms beyond plain zeta sweeps one array only needs submask/superset aggregation, the indexing law is additive, or the mask is just an evolving subset DP state FWHT / XOR Convolution / Subset Convolution Bitwise XOR Convolution
bitset-reachability-shift.cpp one boolean sum axis or component-size reachability row is wide enough that shift-OR over machine words beats scalar subset-sum DP the DP stores values/counts instead of feasibility, the state is the full boolean cube and wants transforms, or plain O(nW) is already tiny Bit-Parallelism / Bitset Optimization School Excursion
broken-profile-domino-tiling.cpp small-width grid domino tilings where one frontier occupancy mask drives current-column to next-column transitions the mask is really a subset of items, full plug connectivity labels are required, or both grid dimensions are too large for 2^h Broken Profile / Plug DP Counting Tilings
tree-dp-subtree.cpp child-to-parent subtree states solved in one postorder DFS each node also needs parent-side information Tree DP Tree Matching
tree-dp-rerooting.cpp sum-of-distances rerooting where every node needs an answer the reroot transition is not this distance-sum formula or you only need one rooted answer Tree DP Tree Distances II
digit-dp-skeleton.cpp count over digits with tight and started flags the state is not prefix-closed by decimal digits Digit DP Counting Numbers
divide-and-conquer-dp.cpp one partition-DP row cur[i] = min(prev[k] + cost(k+1, i)) with monotone argmins and cheap interval cost the transition is affine, the state is interval-shaped, or monotone split points have not been proved Divide and Conquer DP Ciel and Gondolas
knuth-optimization.cpp split-point interval DP dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost(l, r)) with additive interval cost and Knuth opt windows the state is one partition row, the extra cost still depends on k, or monotone opt bounds are not justified Knuth Optimization Knuth Division
interval-dp.cpp split-point interval DP with contiguous intervals [l, r] transitions are endpoint-choice style or dependencies are not interval-shaped Interval DP Interval DP Ladder
li-chao-tree.cpp affine DP or line-container queries with online insertion and a known integer x-domain monotone hull is enough, or lines are only active on x-subsegments Convex Hull Trick / Li Chao Tree Monster Game II
aliens-trick-nonadjacent-max.cpp exact-K non-adjacent weighted picks where one integer penalty per pick makes the relaxed DP linear and the solver must return (value, count) plain O(nK) DP already fits, the transition is really one split-point row, or the relaxed solver cannot return a monotone count under the right tie-break Lagrangian Relaxation / Aliens Trick Red and Blue Lamps
slope-trick-basic.cpp one convex piecewise-linear DP state over integer x updated by max(0, x-a), max(0, a-x), |x-a|, or bounded argmin shifts the transition is affine, the problem is only plain median maintenance, or you need full function reconstruction instead of min value + minimizer interval Slope Trick Snuketoon

Advanced

Advanced Chooser

Template Signal Avoid when Teaching anchor Representative use
meet-in-the-middle-subset-sum.cpp one subset-like exact search where 2^n is too large but two half-sum enumerations plus a cheap merge still fit overlapping subproblems already collapse into DP, strong pruning already makes backtracking cleaner, or the merge layer is as hard as the original search Meet-In-The-Middle Meet in the Middle
ski-rental-threshold.cpp one repeated buy-vs-rent decision with hidden horizon, and the point is to compare a deterministic threshold rule against offline OPT the full input is already known offline, the real family is paging/caching, or randomized design is already the intended main tool Online Algorithms Ski Rental
gradient-descent-linear-regression-1d.cpp one smooth loss over full offline data where the exact lesson is fixed-step full-batch gradient descent on one affine predictor the real task is closed-form regression, logistic / probabilistic modeling matters, or you need richer optimizer families than one deterministic batch update Gradient Descent Linear Regression Gradient Descent Benchmark
perceptron-linear-separable.cpp one binary linear classifier on separable data, where examples arrive in deterministic order and the update rule fires only on mistakes the data is not separable, probabilities or convex losses matter, or the task is normal contest modeling rather than a perceptron benchmark Machine Learning Algorithms Perceptron Classification Benchmark
deutsch-jozsa-simulator.cpp one Boolean oracle is promised constant or balanced, and the whole lesson is to preserve the first quantum-algorithm invariant in a classical simulator the promise is gone, the route really needs fuller quantum algorithms, or you want practical classical speedup on explicit truth-table input Quantum Algorithms Deutsch-Jozsa Oracle Benchmark
blelloch-exclusive-scan.cpp one additive scan benchmark where the real lesson is the work-efficient up-sweep / down-sweep tree and work / span reasoning you only need one ordinary prefix-sum pass, the operator is not associative, or the real task is practical threading rather than one parallel-algorithms primitive Parallel Algorithms Parallel Prefix Sum Benchmark
simplex-max-ax-le-b.cpp one small continuous LP already fits maximize c^T x, Ax <= b, x >= 0 and you need the optimum plus one primal assignment integrality matters, the model is obviously min-cost flow / max flow, or the proof lens matters more than the solver Simplex Cheese, If You Please
matroid-intersection-oracle.cpp one explicit ground set, two independence oracles, and maximum cardinality common independence matters more than weights the task is weighted, the ground set is huge / implicit, or matching / xor basis is already the cleaner specialized model Matroid Intersection Pick Your Own Nim

Math

Math Chooser

Template Signal Avoid when Teaching anchor Representative use
modular-arithmetic.cpp repeated powmod and inverse under one fixed prime modulus modulus is composite or changes per query Modular Arithmetic Exponentiation
matrix-exponentiation.cpp small fixed-dimension linear recurrence or repeated linear transition under one modulus the transition is not linear, the dimension is too large, or a recurrence-specific jump like Kitamasa is cleaner Linear Recurrence / Matrix Exponentiation Throwing Dice
berlekamp-massey-kitamasa.cpp known recurrence with moderate order and one huge k, or enough prefix terms to recover the recurrence first recurrence width is tiny enough that the matrix route is simpler, or the sequence is not linear over the trusted field Berlekamp-Massey / Kitamasa K-th Term of Linearly Recurrent Sequence
gaussian-elimination-mod-prime.cpp one dense linear system over a prime modulus, where any valid assignment (or inconsistency) is enough the modulus is composite, the real lane is xor over GF(2), or the task is about repeated matrix transitions rather than solving Ax = b Gaussian Elimination / Linear Algebra System of Linear Equations
xor-basis.cpp subset xor span, representability, or maximum subset xor under xor-any-subset semantics the query is best xor against one stored value, or you need order-statistics / merge variants this starter does not advertise XOR Basis / Linear Basis XMAX - XOR Maximization
sprague-grundy-subtract-set.cpp impartial normal-play game where each component is one bounded integer state and several components combine by xor of Grundy values the game is misere, score-based, partisan, cyclic without reduction, or the intended route is a closed form not advertised by this starter Game Theory / Sprague-Grundy S-Nim
probability-distribution-dp.cpp one random process with repeated discrete steps and a bounded sum/state, where the answer is an exact event probability or expectation from the final PMF the randomness belongs to the algorithm, the process is continuous, or the intended route is a direct closed-form expectation rather than a PMF DP Probability Dice Probability
factorial-binomial-mod.cpp one or many nCk mod prime queries after one precompute max_n >= mod or the modulus is not prime Counting Basics Distributing Apples
burnside-cyclic-necklaces.cpp count colorings of one cycle up to rotation, where Burnside over C_n is the real model and modular arithmetic is only support code reflections matter, the symmetry group is not just cyclic rotations, or the task needs a full cycle-index / inventory treatment Burnside / Pólya / Group Actions Counting Necklaces
extended-gcd-diophantine.cpp need Bezout coefficients, one inverse under composite modulus, or solve ax + by = c prime-mod inverses with many queries are the real task Modular Arithmetic Euclid Problem
chinese-remainder.cpp merge one or many congruences, including non-coprime moduli with gcd consistency checks you only need one inverse or one Bézout witness and not a whole congruence system Chinese Remainder / Linear Congruences General Chinese Remainder
mod-sqrt-tonelli-shanks.cpp recover one square root x^2 ≡ a (mod p) for one prime modulus the modulus is composite, prime-power lifting is required, or the real task is general discrete roots x^k ≡ a (mod p) Modular Square Root / Discrete Root Sqrt Mod
primitive-root-prime.cpp find one primitive root modulo one prime when the distinct prime divisors of p-1 are already cheap to obtain the modulus is composite, a general discrete-root solution is the real task, or 64-bit factorization is the actual bottleneck Primitive Root Primitive Root
pollard-rho-factorize.cpp factor one 64-bit integer into prime factors when trial division is too slow the numbers are small enough for SPF / trial division, or the real task is generator testing after factors are already known Pollard-Rho Factorize
lucas-binomial.cpp huge nCk mod p queries where one factorial table fails but base-p digit decomposition works the modulus is composite, or p is too large for O(p) precompute to be sane Lucas Theorem / Large Binomial Mod Prime Binomial Coefficient (Prime Mod)
mobius-linear-sieve.cpp divisor-side inclusion-exclusion where cnt[d] over multiples and Mobius weights recover exact gcd structure the prime set is tiny enough for ordinary inclusion-exclusion, or you only need one monotone divisor-frequency scan Mobius And Multiplicative Counting Counting Coprime Pairs
dirichlet-convolution-sigma-sum.cpp one summatory arithmetic function opens directly into a divisor-side floor-sum such as sum_{k<=n} sigma(k) the task needs Mobius cancellation over bounded values, or the intended route has already crossed into Du Jiao / Min_25 Dirichlet Convolution / Prefix Sums Of Number-Theoretic Functions Sum of Divisors
du-jiao-prefix-phi-mu.cpp one huge prefix sum of phi or mu where a Dirichlet identity gives a quotient-set recurrence on Q_n the function still opens into one direct divisor-side floor-sum, or the intended route has already crossed into full Min_25 / prime counting Min_25 / Du Jiao Sum of Totient Function
number-theory-basics.cpp gcd/lcm, SPF sieve, and factorization are the real primitives you mainly need modular inverses or convolution Number Theory Basics CRYPTKEY
fft.cpp approximate real/complex FFT or integer convolution with acceptable floating error you need exact modular/integer convolution guarantees FFT / NTT POST2
ntt.cpp exact convolution modulo 998244353 modulus is incompatible or convolution is over reals FFT / NTT Convolution
fps-inv-newton.cpp one truncated FPS inverse A^{-1} mod x^n under 998244353 where a_0 != 0 and NTT multiplication is already trusted you only need one plain convolution, the modulus is not NTT-friendly, or the task really wants wider FPS operators than this starter exposes Polynomial / Formal Power Series Inv of Formal Power Series

Strings

  • chooser table above; this group now exposes the same contract fields as the mature foundations templates

Geometry

Geometry Chooser

Template Signal Avoid when Teaching anchor Representative use
geometry-primitives.cpp orientation, cross/dot, and exact integer predicates are the real base layer the problem is already at polygon or hull level and a higher template fits directly Vector And Orientation Point Location Test
segment-intersection-basic.cpp closed-segment intersection with endpoints and overlap counted you need sweep-line over many segments, not one pair predicate Segment Intersection Line Segment Intersection
shoelace-area.cpp polygon area from ordered boundary vertices vertices are not in boundary order or the polygon is self-intersecting Polygon Area And Point Location Polygon Area
point-in-polygon.cpp classify outside / boundary / inside for a simple polygon the polygon is not simple or you need a higher-dimensional predicate Polygon Area And Point Location Point in Polygon
convex-hull.cpp hull of static points in the plane dynamic hull maintenance or keep-all-collinear-boundary policy is required Convex Hull Convex Hull
minkowski-sum-convex.cpp one convex polygon built from all sums a + b with a in P, b in Q, with repeated sums and point queries only as follow-up stretch the input polygons are not convex or not already in CCW cyclic order Minkowski Sum Mogohu-Rea Idol (stretch)
half-plane-intersection.cpp bounded feasible region from many directed lines or polygon-kernel tasks the region is unbounded, the input is a point cloud, or event ordering is the real bottleneck Half-Plane Intersection Big Brother
closest-pair-sweep.cpp one static planar point set needs the global nearest Euclidean pair the input changes online, the statement is really generic sweep-line over segments, or the boundary rather than proximity is the target Nearest Pair of Points Closest Pair

Standard

Each template should stay compact, contest-usable, and linked back to the teaching page that explains:

  • when to use it
  • why it works
  • the main implementation invariants
  • the common failure cases

Representative Uses In This Repo

__int128 helper

Use __int128 when a single multiplication may already be near 10^18, or when many such products are accumulated exactly.

Typical examples:

  • shoelace area for geometry
  • modular multiplication before taking %
  • prefix sums of large products

Minimal print helper:

static void print_int128(__int128 x) {
    if (x == 0) {
        cout << 0;
        return;
    }
    if (x < 0) {
        cout << '-';
        x = -x;
    }
    string s;
    while (x > 0) {
        s.push_back(char('0' + x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

Keep in mind:

  • __int128 is a GCC/Clang extension, not standard C++
  • it has no normal cin / cout overloads
  • it is great for exact integer arithmetic, but it still has finite range