Problem Pattern Recognition

Quick Revisit
REACH FOR THIS WHEN: you open a new problem and need to identify the technique
KEY DECISION: which algorithm family matches this problem's constraints and structure
QUICK RULE: read constraints first -- N tells you the complexity class, trigger phrases tell you the technique
SEE ALSO: Reduction Patterns

The most important meta-skill for Codeforces progression is not knowing algorithms — it's knowing which algorithm applies. You can memorize every algorithm in this guidebook and still fail a Div 2 C if you can't identify what the problem is asking for.

This file is the "if you see X, think Y" mega-table. Use it as a reference during virtual contests and upsolving.

One sentence to keep at the front of your mind:Constraints narrow the search space; structure chooses the technique. The constraint table tells you which complexity classes are even legal. The trigger-phrase table tells you which technique fits the structure. Neither alone is enough — many problems with n ≤ 2·10^5 are not segment tree problems, and many "minimum" problems are not binary search on answer.

Workflow: read constraints → scan trigger phrases → walk decision tree → check negative triggers → open the technique file.

1 -- By Constraint Size

The single most reliable signal in any competitive programming problem is $n$ . Before reading the statement carefully, glance at the constraints. They almost always tell you the expected time complexity.

Assume roughly $10^{8}$ simple operations per second (with constant-factor slack on CF).

+-------------------+----------------------------+---------------------------------------+
| Constraint        | Target Complexity          | Typical Techniques                    |
+-------------------+----------------------------+---------------------------------------+
| n <= 8-10         | O(n! ) or O(2^n * n)       | brute-force permutations, bitmask DP  |
| n <= 15-20        | O(2^n * n^2) or O(2^(n/2)) | bitmask DP, meet in the middle        |
| n <= 100          | O(n^3)                     | Floyd-Warshall, Gaussian elimination  |
| n <= 400          | O(n^3)                     | same, but watch constant factor       |
| n <= 5000         | O(n^2)                     | 2D DP, brute force + pruning          |
| n <= 10^5         | O(n sqrt(n))               | Mo's algorithm, sqrt decomposition    |
| n <= 2*10^5       | O(n log n)                 | segment tree, sort + sweep            |
| n <= 10^6         | O(n log n) or O(n)         | prefix sums, BIT, linear algorithms   |
| n <= 10^7         | O(n)                       | sieve, linear scan, two pointers      |
| n <= 10^18        | O(log n) or O(sqrt(n))     | binary exponentiation, math formulas  |
+-------------------+----------------------------+---------------------------------------+

Detailed breakdown

$n \leq 10$ -- You can enumerate all permutations ( $10! = 3.6 \times 10^{6}$ ) or all subsets with bitmask DP ( $2^{10} \cdot 10 \approx 10^{4}$ ). Classic examples: TSP on small graph, assignment problem, brute-force "try every ordering." See Bitmask DP, Complete Search.

$n \leq 20$ -- Bitmask DP with $O (2^{n} \cdot n)$ or $O (2^{n} \cdot n^{2})$ fits comfortably. Meet in the Middle splits into two halves of size $\approx 10$ , giving $O (2^{n / 2} \cdot n)$ . Example: subset sum where values are large but $n$ is small, or counting subsets with XOR = $k$ .

$n \leq 100$ -- $O (n^{3})$ algorithms shine. Floyd-Warshall for all-pairs shortest paths, Gaussian Elimination for linear systems, $O (n^{3})$ interval DP. Example: "given a 100-node graph, find shortest paths between all pairs."

$n \leq 400$ -- Still $O (n^{3})$ territory but you need to be careful with constants. Bipartite matching via Hungarian algorithm ( $O (n^{3})$ ) fits here. Heavy $n^{3}$ DP with non-trivial inner work might TLE -- profile if unsure.

$n \leq 5000$ -- $O (n^{2})$ zone. 2D Sequence DP, brute-force with early termination, $O (n^{2})$ LIS variants. Example: edit distance on strings of length 5000, or "for each pair of elements, check some property."

$n \leq 10^{5}$ -- The sweet spot for $O (n \sqrt{n})$ techniques: Mo's Algorithm, Sqrt Decomposition. Also $O (n \log^{2} n)$ algorithms like merge-sort tree. Example: "answer $q$ range queries about distinct elements, offline."

$n \leq 2 \times 10^{5}$ -- The most common CF constraint. $O (n \log n)$ is the target. Segment Tree, BIT, sort-based approaches, Sweep Line. Example: range queries with point updates, coordinate-compressed BIT for inversions.

$n \leq 10^{6}$ -- Need linear or $O (n \log n)$ with tiny constant. Prefix Sums, Difference Arrays, BIT (lighter than seg tree), DSU without path compression overhead worries. Example: "given $10^{6}$ events, compute prefix XOR."

$n \leq 10^{7}$ -- Must be linear or close. Sieve of Eratosthenes, linear DP, Two Pointers. Any $\log$ factor risks TLE. Example: "find all primes up to $10^{7}$ ."

$n \leq 10^{18}$ -- Math problems. $O (\log n)$ via Binary Exponentiation, Matrix Exponentiation for linear recurrences, $O (\sqrt{n})$ for factorization. Example: "compute the $n$ -th Fibonacci number mod $p$ ."

2 -- By Problem Statement Keywords (Trigger Phrase Table)

This is the core lookup table. When you see a phrase in the problem statement, immediately think of the associated technique.

Graph & Shortest Path

If you see...	Think...	Guidebook Reference
"shortest path," all edges weight 1	BFS	BFS
"shortest path," non-negative weights	Dijkstra	Dijkstra
"shortest path," negative edges allowed	Bellman-Ford / SPFA	Bellman-Ford
"shortest path," all pairs, $n \leq 400$	Floyd-Warshall	Floyd-Warshall
"minimum spanning tree"	Kruskal (sparse) / Prim (dense)	Kruskal, Prim
"topological order" / "prerequisites"	Topological sort (Kahn's or DFS)	Topo Sort
"strongly connected components"	Kosaraju / Tarjan SCC	SCC
"bridges" / "articulation points"	Tarjan's bridge-finding	Bridges
"bipartite" / "two-coloring"	BFS/DFS 2-color, bipartite matching	Bipartite
"maximum flow" / "minimum cut"	Max-flow min-cut (Dinic's)	Flows
"minimum cost flow" / "assignment"	MCMF, Hungarian	Min-Cost Flow
"connected components changing over time"	DSU (Union-Find)	DSU
"grid shortest path," unweighted	BFS on grid	BFS
"grid," edge weights 0 or 1	0-1 BFS (deque-based)	BFS
"Euler path" / "Euler circuit"	Hierholzer's algorithm	Euler Path
"functional graph" / each node has out-degree 1	Cycle detection, binary lifting	Functional Graphs

Tree Queries

If you see...	Think...	Guidebook Reference
"tree + queries on paths"	LCA + Euler tour, HLD	LCA, HLD
"tree + queries on subtrees"	Euler tour + BIT / segment tree	Euler Tour
"tree + counting / aggregation per subtree"	DFS order, small-to-large merging	DSU on Tree
"tree + distance queries"	LCA ( $d i s t = d_{u} + d_{v} - 2 d_{l c a}$ )	LCA
"rerooting" / "for every root compute..."	Rerooting DP	Tree DP
"tree + paths through centroid"	Centroid decomposition	Centroid

Range Queries & Data Structures

If you see...	Think...	Guidebook Reference
"queries on ranges, no updates"	Sparse table / prefix sums	Sparse Table, Prefix Sums
"queries on ranges with point updates"	BIT or segment tree	BIT, Seg Tree
"queries on ranges with range updates"	Segment tree + lazy propagation	Lazy Seg Tree
"range minimum / maximum" (static)	Sparse table ( $O (1)$ query)	Sparse Table
"next greater element"	Monotonic stack	Monotonic Stack
"sliding window maximum / minimum"	Monotonic deque	Monotonic Queue
"offline queries, can sort them"	Mo's algorithm	Mo's
"persistent" / "version history"	Persistent segment tree	Persistent Seg
"2D range query with updates"	2D BIT	2D BIT
"order statistics" / "k-th smallest"	Policy-based tree / merge sort tree	Policy DS

Dynamic Programming

If you see...	Think...	Guidebook Reference
"count paths" / "number of ways"	DP or combinatorics	DP Intro
" $n \leq 20$ , find optimal subset"	Bitmask DP	Bitmask DP
"partition into groups" / "assign items to bins"	Bitmask DP over subsets	Bitmask DP
"knapsack" / "weight + value"	Knapsack DP	Knapsack
"edit distance" / "transform string A to B"	Classic 2D DP	2D DP
"LIS" / "longest increasing subsequence"	Patience sorting / BIT	DP Intro
"interval merging" / "parenthesization"	Interval DP	Interval DP
"count numbers in $[L, R]$ with digit property"	Digit DP	Digit DP
"expected value" / "probability"	Probability DP, linearity of $E$	Probability
"DP transitions look like $d p_{i} = min (d p_{j} + f (i, j))$ "	CHT / Li Chao tree	CHT
"DP transition is monotone" / "SMAWK-like"	D&C DP optimization	D&C DP
"sum over subsets" / "superset / subset convolution"	SOS DP	SOS DP

Strings

If you see...	Think...	Guidebook Reference
"string matching" / "find pattern in text"	KMP, Z-function, or hashing	KMP/Z
"palindrome" / "longest palindromic substring"	Manacher's algorithm	Manacher
"lexicographically smallest"	Greedy, suffix array	Suffix Array
"number of distinct substrings"	Suffix array + LCP / suffix automaton	Suffix Array, Suffix Automaton
"multiple patterns to search"	Aho-Corasick	Aho-Corasick
"substring equality / comparison queries"	Hashing	Hashing
"common prefix" / "longest common prefix"	Z-function or suffix array + LCP	KMP/Z
"palindrome decomposition" / "rich in palindromes"	Palindromic tree (Eertree)	Palindromic Tree
"prefix function" / "failure function"	KMP	KMP/Z

Math & Number Theory

If you see...	Think...	Guidebook Reference
"print answer mod $10^{9} + 7$ "	Modular arithmetic, combinatorics	Number Theory
"gcd" / "lcm" / "divisors"	Euclidean algorithm, factorization	Number Theory
"prime" / "factorization"	Sieve, trial division	Number Theory
"modular inverse"	Fermat ( $a^{p - 2} mod p$ ), ext GCD	Number Theory
"Fibonacci" / "linear recurrence"	Matrix exponentiation	Matrix Exp
"matrix multiplication" / "transitions"	Matrix exponentiation	Matrix Exp
"game theory" / "who wins" / "Nim"	Sprague-Grundy theorem	Game Theory
"Catalan" / "balanced parentheses count"	Catalan numbers	Catalan
"derangement" / "no element in original position"	Inclusion-exclusion	Inc-Exc
"choose" / " $(\binom{n}{k})$ " / "combinations"	Precompute factorials, Lucas	Combinatorics
"polynomial multiplication" / "convolution"	FFT / NTT	FFT/NTT
"XOR basis" / "maximize XOR of subset"	Linear basis (Gaussian elim in GF2)	Gaussian Elim
"solve system of linear equations"	Gaussian elimination	Gaussian Elim

Core Techniques & Miscellaneous

If you see...	Think...	Guidebook Reference
"longest subarray/substring such that..."	Sliding window / two pointers	Sliding Window
"number of subarrays with property"	Prefix sums, contribution technique	Prefix Sums, Contribution
"merge intervals" / "overlapping intervals"	Sort + sweep line	Sweep Line
"binary search the answer"	Binary search on answer + check()	Binary Search
"minimize the maximum" / "maximize the minimum"	Binary search on answer	Binary Search
"circular array"	Double the array, modular indexing	Arrays
"binary string operations"	Bitwise DP, greedy, bit tricks	Bit Manipulation
"permutation"	Cycle decomposition, inversions	Sorting
"convex hull" / "upper/lower envelope"	Graham scan, monotone chain	Geometry
"closest pair of points"	Divide & conquer or sweep	Geometry
"coordinate compression needed"	Sort + unique + remap	Coord Compression
"interact with judge" / "? query"	Interactive binary search / strategy	Interactive
"construct any valid answer"	Constructive -- think greedy/invariant	Constructive
"trie" / "prefix queries on strings"	Trie (also bitwise trie for XOR)	Trie
"priority queue" / "always take smallest"	Min-heap / greedy	Heaps
"range add + point query"	Difference array	Difference Arrays
"randomized" / "probabilistic"	Hashing, random shuffle, treap	Randomization

Negative triggers — when the obvious match is wrong

Trigger phrases are starting hypotheses, not conclusions. The same phrase maps to different techniques depending on the rest of the structure. Below are the most common misfires.

Phrase / tag	Looks like…	But actually…
"minimum X"	binary search on answer	Often plain greedy / sorting / DP. Binary search needs monotone feasibility — if "achievable at $k$ " doesn't imply "achievable at $k + 1$ ", binary search is wrong.
"maximum X subject to constraint"	binary search on answer	Same caveat. Many "max sum subarray" / "max product subset" problems are pure DP.
"tree with queries"	HLD or centroid decomposition	Often Euler tour + BIT, LCA + difference, or rerooting. HLD is the heavy hammer; reach for it only when path updates are involved.
"count number of ways"	DP	Sometimes pure combinatorics, generating functions, or matrix exponentiation when $n$ is huge.
"shortest path"	Dijkstra / BFS	If $n \leq 20$ and you must visit a subset, it's bitmask DP. If edges are 0/1, it's 0-1 BFS. If negative cycles are possible, it's Bellman-Ford or SPFA.
" $n \leq 2 \cdot 10^{5}$ " + "range"	segment tree	Often prefix sums, sweep line, monotonic stack, or offline sorting. Segment tree is overkill if there are no updates.
"string matching"	KMP / Z-function	If you only need to test equality of two substrings, hashing is simpler. If many patterns at once, Aho-Corasick.
"for every node as root"	rerooting	Only if the combine is invertible or admits a prefix/suffix or best/second-best decomposition. Otherwise centroid decomposition.
"expected value"	probability DP	Often linearity of expectation collapses the entire problem to a one-line sum. Don't reach for DP until you've tried indicator variables.
CF tag `dp`	DP	The problem may be solvable by greedy or a closed form; the tag only means some solution uses DP, not that DP is required.
"operation until impossible"	simulation	Usually an invariant problem: find the conserved quantity instead of simulating.

The pattern: when a phrase narrows you to one technique, take 30 seconds to stress-test that match against the constraints and against an alternative. The alternative is almost always greedy, sorting, or a contribution reframe — and it's almost always cleaner when it works.

3 -- By Codeforces Tag

Common CF tags mapped to techniques and the rating range where they first become essential.

CF Tag	Core Techniques	First Appears	Peaks At
implementation	Simulation, careful coding	800	800-1200
math	Modular arithmetic, number theory, combinatorics	800	1200-1800
greedy	Sorting + invariant arguments, exchange arguments	900	1200-1600
dp	1D, 2D, bitmask, digit, tree, optimization tricks	1000	1400-2100
data structures	Seg tree, BIT, DSU, sparse table, stacks/queues	1200	1600-2100
graphs	BFS, DFS, shortest paths, MST, connectivity	1200	1400-1800
strings	Hashing, KMP, Z, suffix structures	1300	1600-2100
number theory	Sieve, GCD, modular inverse, Euler's totient	1200	1400-1800
combinatorics	Binomial coefficients, stars-and-bars, PIE	1300	1600-2100
binary search	Search on answer, lower_bound tricks	1100	1200-1600
two pointers	Sliding window, merge-like scans	1100	1200-1500
sortings	Custom comparators, sweep events	800	1000-1400
constructive algorithms	Build a valid solution from invariants	1000	1200-1800
brute force	Complete search, small constraints	800	800-1200
dfs and similar	DFS tree, back edges, tree traversals	1200	1400-1800
trees	LCA, Euler tour, tree DP, rerooting	1300	1600-2100
flows	Max-flow, min-cut, bipartite matching	1800	2000+
geometry	Convex hull, sweep, cross product	1500	1800-2100
bitmasks	Bitmask DP, SOS DP, subset enumeration	1300	1500-1800
divide and conquer	Merge sort applications, CDQ	1400	1600-2000
games	Sprague-Grundy, Nim, game DP	1400	1600-2000
probabilities	Linearity of expectation, probability DP	1500	1800-2100
matrices	Matrix exponentiation, Gaussian elimination	1600	1800-2100
fft	Polynomial multiplication, NTT, generating funcs	1900	2100+

4 -- By Rating Band

CF 800-1000: Fundamentals

Techniques: if/else, loops, basic arrays, simple math (divisibility, parity).

Typical problems:

"Find the maximum element" -- one pass scan.
"Is $n$ divisible by both $a$ and $b$ ?" -- check n % a == 0 && n % b == 0.
"Simulate the process described" -- careful implementation.
"Given a string, count vowels" -- single traversal with conditions.

Almost everything here is implementation. Speed comes from reading carefully, coding cleanly, and handling edge cases (especially $n = 0$ or $n = 1$ ). Don't overthink -- if constraints are tiny and the statement describes a process, just simulate it.

Common pitfalls: integer overflow (use long long when products exceed $2 \times 10^{9}$ ), off-by-one errors, not reading the problem statement carefully enough.

CF 1000-1200: Simple Greedy & Sorting

New techniques: sorting + greedy, frequency counting, basic string manipulation, simple simulation with state.

Typical problems:

"Rearrange elements to maximize something" -- sort and pick greedily.
"Count characters with certain frequency" -- frequency array.
"Find minimum operations to equalize" -- sort, median insight.
"Can you partition into pairs satisfying a condition?" -- sort, greedy pairing.
"Process events in order" -- sort by time, simulate.

The key insight at this level: most problems have a clean greedy solution after sorting. If you're writing nested loops or complicated DP for a 1000-rated problem, step back and look for a simpler approach.

See Greedy, Sorting.

CF 1200-1400: Binary Search, Prefix Sums, Basic Graph

New techniques: Binary Search, Two Pointers, Prefix Sums, basic BFS/DFS, simple 1D DP, Constructive Algorithms.

Typical problems:

"Find minimum time such that we can achieve X" -- binary search on answer.
"Longest subarray with sum $\leq k$ " -- sliding window.
"Shortest path in unweighted grid" -- BFS.
"Count subsequences" / "max sum subsequence" -- basic DP.
"Construct a permutation with given properties" -- constructive + invariant.

This is the band where algorithmic thinking first matters more than implementation speed. You need to recognize that "minimize the maximum" almost always means binary search on answer. If you're stuck, ask: "Can I binary search the answer and check feasibility?"

CF 1400-1600: Segment Trees, Graph Shortest Paths, Intermediate DP

New techniques: Segment Tree, BIT, Dijkstra, DSU, Number Theory (sieve, modular inverse), Knapsack DP, Topological Sort.

Typical problems:

"Range sum queries with point updates" -- BIT or segment tree.
"Shortest path in weighted graph" -- Dijkstra with priority queue.
"Check if graph is bipartite" -- BFS 2-coloring.
" $(\binom{n}{k}) mod 10^{9} + 7$ " -- precompute factorials + inverse.
"Process dependencies / course prerequisites" -- topological sort.
"Merge overlapping intervals" -- sort by left endpoint + sweep.

The jump from 1200 to 1400 is where most people plateau. The key: you need a toolkit of ~10 standard algorithms and the ability to recognize when each applies. Drill segment tree and Dijkstra until they're second nature.

CF 1600-1800: Advanced DP, SCC, Combinatorics

New techniques: Bitmask DP, Digit DP, Tree DP, SCC, Bridges, Combinatorics, Inclusion-Exclusion, Lazy Propagation, Game Theory.

Typical problems:

"TSP variant with $n \leq 18$ " -- bitmask DP.
"Count integers in $[L, R]$ with digit-sum property" -- digit DP.
"Find all bridges in a graph" -- Tarjan's algorithm.
"2-SAT satisfiability" -- SCC implication graph.
"Nim-like game, who wins?" -- Sprague-Grundy analysis.
"Range update + range query" -- lazy segment tree.

This is the "intermediate plateau." Problems start combining two ideas (e.g., binary search + greedy check, or graph modeling + DP). The ability to reduce an unfamiliar problem to a known technique is more important than knowing exotic algorithms.

CF 1800-2100: Centroid Decomp, Flows, FFT, Advanced Strings

New techniques: Centroid Decomposition, HLD, Max Flow, FFT/NTT, Suffix Array, CHT/Li Chao, D&C DP Optimization, Mo's Algorithm.

Typical problems:

"Path queries on tree with updates" -- HLD + segment tree.
"Count pairs in tree with distance $\leq k$ " -- centroid decomposition.
"Polynomial multiplication" -- FFT.
"Min-cut in flow network" -- Dinic's algorithm.
"DP with transition $d p_{i} = min_{j} (d p_{j} + c o s t (j, i))$ and convex cost" -- CHT.
"Offline range distinct count" -- Mo's algorithm.

At this level, you often need to model the problem as a graph or reduce it to a known structure before applying the algorithm. The problem statement won't say "find the maximum flow" -- it'll describe a scenario that is a flow problem.

CF 2100+: Beyond

Hallmarks: combining 2-3 techniques, reduction to known problems, heavy math, Slope Trick, SOS DP, CDQ D&C, Suffix Automaton, Palindromic Tree, Parallel Binary Search.

Problems at this level rarely have a single "trick" -- they require composing ideas. Example: "persistent segment tree on centroid decomposition tree" or "FFT to speed up a DP convolution." You need fluency in the building blocks so you can focus on the novel reduction step.

5 -- Decision Trees

5.1 Graph Problem Decision Tree

                     I have a GRAPH problem
                              |
              +---------------+----------------+
              |               |                |
         Shortest path?   Connectivity?    Optimization?
              |               |                |
              v               v                v
         Weighted?       Components?      MST? Flow?
         /      \         /      \         /       \
        No      Yes     Static  Dynamic   MST      Flow
        |       |        |        |        |         |
       BFS   Negative?  DFS/    DSU     Kruskal   Bipartite
              /    \    BFS              /Prim     matching?
             No    Yes                            /       \
             |      |                           Yes        No
          Dijkstra  |                            |          |
                  All pairs?                  Hungarian   Dinic's
                  /       \                   /MCMF       max-flow
                Yes        No
                 |          |
            Floyd-      Bellman-
            Warshall    Ford/SPFA

                Connectivity sub-tree
                        |
            +-----------+-----------+
            |           |           |
        Undirected?  Directed?   Bipartite?
            |           |           |
            v           v           v
        Bridges/     SCC         2-color
        artic pts  (Tarjan/       BFS
        (Tarjan)   Kosaraju)      |
            |           |      Matching?
        Bridge-      Topo         |
        tree         sort      Hopcroft-
                     (DAG)     Kroft / Kuhn

5.2 Range Query Decision Tree

           I have a RANGE QUERY problem
                       |
               Static or Dynamic?
               /                \
           Static              Dynamic
           (no updates)        (has updates)
           /        \              |
      Idempotent?   No       Point or Range update?
      (min/max/gcd)  |          /            \
          |        Prefix    Point           Range
          v        sums      update          update
      Sparse       /  \        |               |
      table    1D    2D    Need what?       Lazy seg
      O(1)                  /      \         tree
      query             Simple   Complex       |
                        (sum,    (merge,    Need what?
                        xor)     custom)    /        \
                         |         |     Additive   Complex
                        BIT     Seg tree    |          |
                                          BIT +     Lazy seg
                                          diff arr  tree

5.3 String Problem Decision Tree

            I have a STRING problem
                      |
          +-----------+-----------+
          |           |           |
      Matching?  Palindrome?   Counting?
          |           |           |
          v           v           v
     Single or   Longest?   Distinct
     multiple    /      \   substrings?
     patterns?  Sub-    Sub-      |
      /    \    string  sequence  Suffix
   Single  Multi  |      |       array
     |       |  Manacher  DP     + LCP
     v       v                   or SAM
   KMP/Z  Aho-
   func   Corasick
     |
   Need O(1)
   substring
   comparison?
     |
   String
   hashing

5.4 Subset / Counting Problem Decision Tree

         I need to COUNT or OPTIMIZE over SUBSETS
                         |
                  How large is n?
                /        |         \
           n <= 20    n <= 40     n is large
              |          |           |
              v          v           v
         Bitmask     Meet in     Not subsets --
         DP          the middle  rethink as DP,
         O(2^n * n)  O(2^(n/2)) greedy, or math
              |
         Need sum over
         all subsets?
         /          \
        Yes          No
         |            |
       SOS DP     Standard
       O(2^n * n) bitmask DP

How to use this file

The recommended workflow when you open a new problem (target: under two minutes for recognition):

Read constraints first. Jump to Section 1. The value of $n$ immediately narrows the complexity class and eliminates most techniques.
Scan for trigger phrases. Read the problem statement and look up keywords in Section 2. "Shortest path with negative edges" -> Bellman-Ford. Done.
Check the CF tag (if practicing on CF). Section 3 tells you what techniques are commonly associated with each tag and at what rating they appear.
Match your rating band. Section 4 tells you what techniques you should expect at your current level. If a 1400-rated problem mentions "range queries," it's almost certainly BIT or basic segment tree, not persistent seg tree.
Walk the decision tree. If the problem type is clear (graph, range query, string, subset), follow the appropriate flowchart in Section 5.
Open the technique file. Every entry in the tables links to a detailed file with theory, implementation, and practice problems.

The goal is to spend less than 2 minutes identifying the technique, so you can spend the remaining time on implementation and edge cases. Pattern recognition is a muscle -- the more problems you solve, the faster this lookup becomes automatic.

Common Mistakes in Choosing

Constraint blindness. You see "shortest path" and immediately think Dijkstra, but $n \leq 20$ . You should think bitmask DP + BFS, or even brute force. Always check constraints before choosing an algorithm.
Overcomplicating. A 1200-rated problem rarely needs a segment tree. If your solution feels too complex for the rating, there's probably a simpler approach. Step back and look for greedy or prefix-sum solutions.
Missing the reduction. Many problems don't directly state "find shortest path." They describe a scenario that models as a graph problem. Practice translating problem descriptions into abstract structures.
Ignoring the output format. "Print any valid answer" -> constructive/greedy. "Print the answer modulo $10^{9} + 7$ " -> DP or combinatorics (not simulation). "Print YES/NO" -> often binary search or 2-coloring.

Mental traps

"I've seen this pattern before, so I know the solution." Two problems with the same surface phrasing can have completely different solutions. "Count subarrays with sum ≤ k" looks like sliding window — but if values can be negative, sliding window fails. Pattern recognition generates the starting hypothesis, not the ending conclusion.

"The trigger phrase table IS the skill." The table is a training aid. The actual skill is an internalized reflex built from solving hundreds of problems. If you're paging through tables mid-contest, you're too slow.

"I need to recognize the exact technique, not just the category." At the recognition step you only need the category (graph, DP, range query) and complexity class. The specific technique comes from thinking about the structure once the category is fixed. Racing to name the specific algorithm leads to wrong commitments.

"Complex problems have complex patterns." Hard problems usually combine simple components with a subtle connection. "Count paths in a tree" + "sum along path" reduces to centroid decomposition + sorting. The difficulty is in the combination, not in any single pattern being exotic.

Self-Test

Drawn from reflection notes

Without opening any reference:

[ ] Speed drill: Take 5 random CF problems at your rating +200. For each, spend exactly 3 minutes and write down: (a) the complexity class from constraints, (b) the problem category, (c) the technique you'd try first. Don't code -- this isolates the recognition skill.
[ ] Trigger phrase drill: Cover the "Think..." column in the trigger phrase table. Read each "If you see..." entry and fill in the technique from memory. Score yourself honestly.
[ ] Constraint mismatch exercise: Pick any technique (e.g., Dijkstra). Write 3 problem contexts where "shortest path" appears but Dijkstra is wrong (wrong constraints, wrong structure). This builds the "verify, don't just recognize" habit.
[ ] Rating calibration: For 3 techniques you know well, state the typical CF rating range where they first appear. If you're off by more than 200 points, your pattern calibration needs work.
[ ] One-sentence reduction: Take any solved problem and write: "This is a [category] problem because [structural property] maps to [technique]." If you can't name the structural property, you've memorized the solution without extracting the pattern.

Difficulty: N/A (universal reference) | CF Rating Range: 1100-2100 | No prerequisites.

The problem never tells you which algorithm to use -- but the constraints do. An n <= 20 screams bitmask, n <= 5000 whispers O(n^2), and "query on subarray" is a love letter to segment trees. Learn to read the problem through the lens of what the limits permit, not what the statement describes.

When you feel stuck, don't re-read the statement hoping for inspiration. Instead, (1) list the constraints (n, q, time limit), (2) compute the maximum operations allowed, (3) match the required complexity to a short-list of techniques, and (4) check which technique's preconditions the problem satisfies.

Rating Progression

CF Rating	What to Master
1200	Memorize the basic "if n <= X, think Y" table: n <= 20 -> bitmask/brute-force, n <= 5000 -> O(n^2) DP, n <= 10^5 -> sorting/binary search/greedy, n <= 10^6 -> linear algorithms. Recognize standard problem archetypes (knapsack, shortest path, LIS).
1500	Identify structural signals: "tree + queries" -> Euler tour + data structure, "grid + BFS" -> 0-1 BFS or multi-source BFS, "string matching" -> hashing or KMP. Start building a personal "if X then Y" lookup table from solved problems.
1800	Recognize reductions: "this looks like max-flow," "this is bipartite matching in disguise," "the constraint graph is a DAG so topo-sort + DP." Practice converting novel-sounding stories into known graph/DP models. Handle combined techniques (e.g., binary search + greedy check, DP + segment tree optimization).
2100	Spot subtle patterns: "the operation is XOR so think linear algebra over GF(2)," "the answer is convex so use CHT/Li Chao," "the transitions form a monoid so use matrix exponentiation." Build intuition for when a problem is designed to use a specific technique based on editorial meta-patterns.

Before You Code Checklist

[ ] Read constraints first: Written down n, m, q, and time/memory limits. Computed the max operations budget (approx 3-5 x 10^8 simple ops per second).
[ ] Named the problem type: Identified whether this is optimization, counting, decision, or construction -- this filters which technique families apply.
[ ] Listed candidate techniques: Based on constraints, wrote down 2-3 plausible algorithm families (e.g., "O(n log n) -> segment tree, merge sort tree, or binary search + BIT").
[ ] Checked structural preconditions: For each candidate, verified the problem has the right structure (e.g., "Is this actually a DAG?" "Is the function monotone for binary search?" "Is the DP transition invertible for rerooting?").
[ ] Solved a small example by hand: Traced through n = 4 or 5 to confirm your model matches the problem before writing code.

What Would You Do If...?

Scenario 1: n <= 2 x 10^5 and the problem asks for the minimum cost to partition an array. You think it's DP, but O(n^2) DP is too slow. What next?

Answer: Check if the DP transition has special structure. If the cost function is convex -> divide-and-conquer optimization or SMAWK. If it's of the form dp[j] + f(i,j) where f decomposes as a[i]*b[j] -> convex hull trick. If the transition accesses only a sliding window -> deque optimization. The key is to classify the shape of the transition, not just the DP itself.

Scenario 2: You see "find the maximum number of non-overlapping intervals" and immediately think greedy. But the problem adds weights to each interval. Does greedy still work?

Answer: No -- weighted interval scheduling is not solvable by the classic "sort by end time" greedy. It becomes a DP problem: sort by end time, then dp[i] = max(dp[i-1], w[i] + dp[last_non_overlapping[i]]), with binary search to find the last compatible interval. The signal that greedy breaks is the word "weighted" -- unweighted selection is greedy, weighted selection is DP.

Scenario 3: The problem gives a tree with n <= 10^5 and asks for the answer "for every node as root." You've never seen this pattern before.

Answer: This is the rerooting pattern. The structural signal is literally "for every node as root" or "for all possible roots." Compute a standard rooted-tree DP in one DFS, then propagate the answer to all roots in a second DFS by shifting contributions along each edge. See the rerooting chapter for the full technique.

The Mistake That Teaches

During a Codeforces round, I saw this problem: given n <= 2 x 10^5 points on a line, find the minimum number of groups such that the max minus min within each group is <= k.

I immediately thought: "Intervals! Grouping! This is interval scheduling!" I spent 25 minutes trying to reduce it to interval covering with greedy, building intervals [a_i, a_i + k] and trying to find a minimum cover. It kept failing edge cases.

With 15 minutes left, I stepped back and asked: "What does the constraint actually allow?" Sort the points. Then greedily start a new group whenever the current point exceeds the first point in the current group by more than k. That's it -- a simple greedy on the sorted array, O(n log n).

My mistake was pattern-matching to a similar-sounding but wrong template. "Grouping with constraints" made me think of interval scheduling, but the actual structure was much simpler. The lesson: before reaching for a complex technique, ask "is there a trivial approach that the constraints permit?" The sort-and-scan approach was O(n log n), well within budget, and needed zero data structures.

I now have a rule: spend 2 minutes on the simplest possible approach before going to the technique lookup table. Half the problems at CF <= 1800 are solvable with sorting + a single pass.

Debug This

Bug 1: Wrong algorithm choice -- using DFS when BFS is needed.

cpp

// Problem: Find shortest path in an unweighted grid from (0,0) to (n-1,m-1)
int dist[MAXN][MAXM];
bool vis[MAXN][MAXM];

void dfs(int x, int y, int d) {
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (vis[x][y]) return;
    vis[x][y] = true;
    dist[x][y] = d;
    dfs(x+1, y, d+1);
    dfs(x-1, y, d+1);
    dfs(x, y+1, d+1);
    dfs(x, y-1, d+1);
}
// Call: dfs(0, 0, 0);
// Answer: dist[n-1][m-1]

What's the bug?

DFS does not find shortest paths in unweighted graphs -- it explores one branch fully before backtracking, so dist[x][y] will hold the first-discovered distance, not the shortest. The fix is to replace DFS with BFS (use a queue), which processes nodes in order of increasing distance and guarantees shortest paths in unweighted graphs.

Bug 2: Choosing O(n^2) DP when greedy suffices -- the code is correct but TLEs.

cpp

// Problem: Given n <= 10^6 activities with start/end times, find max
// non-overlapping activities (unweighted).
// Approach: O(n^2) DP
sort(activities.begin(), activities.end(), by_end_time);
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
    dp[i] = dp[i-1];
    for (int j = i-1; j >= 0; j--) {
        if (activities[j].end <= activities[i].start) {
            dp[i] = max(dp[i], dp[j] + 1);
            break;
        }
    }
}
cout << dp[n-1] << endl;

What's the bug?

This isn't a code bug -- it's an algorithm selection bug. Unweighted activity selection (a.k.a. interval scheduling maximization) is a classic greedy problem: sort by end time, then greedily pick each activity whose start >= last picked end. That's O(n log n). The O(n^2) DP is correct but far too slow for n = 10^6. The lesson: always check if a greedy solution exists before reaching for DP.

Bug 3: Binary search used without verifying monotonicity.

cpp

// Problem: Find the minimum value of x such that f(x) >= target
// f(x) = (x % 7) + x/3   (not monotone!)
int lo = 0, hi = 1e9;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (f(mid) >= target)
        hi = mid;
    else
        lo = mid + 1;
}
cout << lo << endl;

What's the bug?

Binary search requires the predicate to be monotone -- once f(x) >= target becomes true, it must stay true for all larger x. But f(x) = (x % 7) + x/3 is not monotone: the x % 7 term oscillates, so there can be values where f(x) >= target is true, then false again at x+1. The binary search may converge to a wrong answer. Fix: either prove monotonicity before using binary search, or use a linear/ternary search appropriate for the function's actual shape.

Cross-References

Reduction Patterns -- converting unfamiliar problems into known ones
Data Structure Selection Guide -- choosing the right DS for your constraints
Practice Ladders -- graded problem sets organized by technique

Problem Pattern Recognition ​

1 -- By Constraint Size ​

Detailed breakdown ​

2 -- By Problem Statement Keywords (Trigger Phrase Table) ​

Graph & Shortest Path ​

Tree Queries ​

Range Queries & Data Structures ​

Dynamic Programming ​

Strings ​

Math & Number Theory ​

Core Techniques & Miscellaneous ​

Negative triggers — when the obvious match is wrong ​

3 -- By Codeforces Tag ​

4 -- By Rating Band ​

CF 800-1000: Fundamentals ​

CF 1000-1200: Simple Greedy & Sorting ​

CF 1200-1400: Binary Search, Prefix Sums, Basic Graph ​

CF 1400-1600: Segment Trees, Graph Shortest Paths, Intermediate DP ​

CF 1600-1800: Advanced DP, SCC, Combinatorics ​

CF 1800-2100: Centroid Decomp, Flows, FFT, Advanced Strings ​

CF 2100+: Beyond ​

5 -- Decision Trees ​

5.1 Graph Problem Decision Tree ​

5.2 Range Query Decision Tree ​

5.3 String Problem Decision Tree ​

5.4 Subset / Counting Problem Decision Tree ​

How to use this file ​

Common Mistakes in Choosing ​

Mental traps ​

Self-Test ​

Rating Progression ​

Before You Code Checklist ​

What Would You Do If...? ​

The Mistake That Teaches ​

Debug This ​

Cross-References ​

Problem Pattern Recognition

1 -- By Constraint Size

Detailed breakdown

2 -- By Problem Statement Keywords (Trigger Phrase Table)

Graph & Shortest Path

Tree Queries

Range Queries & Data Structures

Dynamic Programming

Strings

Math & Number Theory

Core Techniques & Miscellaneous

Negative triggers — when the obvious match is wrong

3 -- By Codeforces Tag

4 -- By Rating Band

CF 800-1000: Fundamentals

CF 1000-1200: Simple Greedy & Sorting

CF 1200-1400: Binary Search, Prefix Sums, Basic Graph

CF 1400-1600: Segment Trees, Graph Shortest Paths, Intermediate DP

CF 1600-1800: Advanced DP, SCC, Combinatorics

CF 1800-2100: Centroid Decomp, Flows, FFT, Advanced Strings

CF 2100+: Beyond

5 -- Decision Trees

5.1 Graph Problem Decision Tree

5.2 Range Query Decision Tree

5.3 String Problem Decision Tree

5.4 Subset / Counting Problem Decision Tree

How to use this file

Common Mistakes in Choosing

Mental traps

Self-Test

Rating Progression

Before You Code Checklist

What Would You Do If...?

The Mistake That Teaches

Debug This

Cross-References