If You See X, Think Y

Quick Revisit

• REACH FOR THIS WHEN: you are stuck on a problem and need the right technique to pop into your head
• KEY DECISION: which trigger phrase in the problem statement maps to which algorithmic technique
• QUICK RULE: identify the trigger, look up the reduction, verify it applies, then implement
• SEE ALSO: Problem Pattern Recognition, Graph Modeling

A working competitive programmer's pattern-matching cheat sheet. Not a substitute for understanding -- but a shortcut to the right idea when you're stuck and the clock is ticking.

This catalog is organized by trigger -- the shape of the problem statement that should make a particular technique pop into your head. Each entry is deliberately brief: the trigger, the reduction, and one concrete example.

---

Optimization & Search

"Minimize the maximum" or "maximize the minimum." --> Binary search on the answer. The decision version is almost always greedy. Example: Place $k$ cows to maximize minimum distance --> binary search on distance $D$, greedily place.

"Find the optimal value of X." --> If checking "is X achievable?" is easier and monotonic, binary search on X. Example: Minimum time for $k$ machines to produce $n$ items --> "can they produce $n$ in time $T$?"

"Lexicographically smallest sequence." --> Greedy: at each step, choose the smallest valid option. Often pair with a set or priority queue to efficiently find the smallest valid choice. Example: Lexicographically smallest topological order --> use a min-heap instead of a queue in Kahn's algorithm.

"Count the number of ways." --> Often DP, but first ask whether the choices have local state or a closed form. Counting problems also live in pure combinatorics (binomials, stars-and-bars), inclusion-exclusion, generating functions, matrix exponentiation (linear recurrences with huge $n$), and Burnside-style symmetry counting. DP is the safe default; the better answer often isn't. Example: Number of paths in a grid --> DP, dp[i][j] = dp[i-1][j] + dp[i][j-1].Example: Paths in an $H\times W$ grid with no obstacles --> closed form $(\genfrac{}{}{0ex}{}{H+W-2}{H-1})$, no DP needed.Example: Number of length-$n$ strings avoiding a pattern, $n\le {10}^{18}$ --> matrix exponentiation on the KMP automaton, not 1D DP.

---

Counting & Summation

"Counting pairs with a property." --> Fix one element, count valid partners with binary search, two pointers, or a hash map. Example: Count pairs with sum = $k$ --> for each $a_i$, check if $k-a_i$ exists in a hash set.

"Sum over all pairs / subarrays / subsets." --> Contribution technique: for each element, count how many structures it appears in. Example: Sum of all subarray sums --> element $a[i]$ appears in $(i+1)\times (n-i)$ subarrays.

"Expected value of some quantity." --> Linearity of expectation. Decompose into indicator random variables, compute each expectation separately. Example: Expected number of inversions in a random permutation --> each pair is inverted with probability $1/2$, so $E=(\genfrac{}{}{0ex}{}{n}{2})/2$.

"Count valid configurations" (complex constraints). --> Complement: total minus invalid. Or inclusion-exclusion if there are multiple overlapping bad conditions. Example: Derangements --> $n!-(\genfrac{}{}{0ex}{}{n}{1})(n-1)!+(\genfrac{}{}{0ex}{}{n}{2})(n-2)!-\dots$ (inclusion-exclusion).

---

Graph Reductions

"Connected components changing over time." --> If the queries can go offline and the updates are deletion-only or addition-only, process them in reverse so deletions become additions, and use DSU. If edges arrive and depart in arbitrary online order, this trigger does not apply — that's fully dynamic connectivity, a much harder tier (link-cut trees, Holm-Lichtenberg-Thorup, or seg-tree-over-time + rollback DSU when intervals are known). Example: Edges deleted one by one, query components offline --> reverse the deletions, add edges with DSU.

"Shortest path with constraints" (fuel, keys, time windows). --> Layered graph: node = (position, constraint state). Run Dijkstra/BFS on the layered graph. Example: Shortest path collecting keys --> state = (position, bitmask of keys held).

"Minimum cost to connect everything." --> MST (Kruskal's or Prim's). Example: Connect cities with minimum cable cost --> MST on the city graph.

"Can we split into two groups with no conflicts?" --> Bipartiteness check (BFS/DFS 2-coloring). Example: Two-color a graph so no adjacent nodes share a color --> bipartite check.

"Reachability or dependency ordering." --> Topological sort on a DAG. If there's a cycle, the answer is "impossible." Example: Course prerequisites --> Kahn's algorithm; the schedule is valid iff all $n$ courses are processed (ordered) before the queue empties. "Reachable" is a different graph property — don't conflate them.

---

Game Theory

"Game with alternating moves, optimal play." --> If the game is impartial (same moves for both players): Sprague-Grundy theorem. Compute Grundy values. XOR them for combined games. Example: Nim --> XOR of all pile sizes. Zero = losing, nonzero = winning.

"Game on a graph/tree." --> Work backward from terminal states. A state is W if any move leads to L; L if all moves lead to W. Example: Mouse on a graph, cat chases --> BFS backward from terminal states with (mouse_pos, cat_pos, turn).

---

Strings

"Substring matching or searching." --> Hashing (Rabin-Karp) for randomized $O(n)$, KMP or Z-function for deterministic. Example: Find all occurrences of pattern in text --> KMP automaton.

"Longest common substring / prefix." --> Suffix array + LCP array. Or hashing + binary search on length. Example: Longest repeated substring --> max value in LCP array.

"All distinct substrings." --> Suffix automaton (each state corresponds to an equivalence class of right-extensions) or suffix array with LCP. Example: Count distinct substrings via SAM --> sum $\text{len}[v]-\text{len}[\text{link}[v]]$ over all non-initial states. (Counting reachable states is not the right formula — each state stores a range of lengths, so distinct substrings = sum of range widths.)Example: Count distinct substrings via suffix array --> $(\genfrac{}{}{0ex}{}{n+1}{2})-\sum _i\text{lcp}[i]$, which equals $\sum _i(n-sa[i]-\text{lcp}[i])$ when indexing the suffix array conventionally.

---

Data Structure Signals

"Range queries + point updates." --> Fenwick tree (if the operation is invertible, e.g., sum) or segment tree (general). Example: Range sum with point updates --> Fenwick tree.

"Range updates + range queries." --> Segment tree with lazy propagation. Example: Range add, range sum --> lazy segment tree.

"Merge sets / check connectivity dynamically." --> Disjoint Set Union (DSU) with union by rank and path compression. Example: Dynamic connectivity as edges arrive --> DSU.

"Sliding window maximum/minimum." --> Monotonic deque (or sparse table if the window is query-based). Example: Max in every window of size $k$ --> deque, $O(n)$.

"Predecessor / successor queries." --> Balanced BST (C++ std::set) or van Emde Boas tree for integer universe. Example: "Find the largest element <= X" --> set::upper_bound, then decrement.

---

Permutations & Combinatorics

"Permutation with constraints." --> Model as a graph. Each $p[i]=j$ is a directed edge $i\to j$. Permutations decompose into cycles. Example: Minimum swaps to sort --> $n$ minus the number of cycles.

"Divide items into groups with constraints." --> Bipartite matching if assigning items to slots with compatibility. Bitmask DP if $n$ is small ($\le 20$). Example: Assign $n$ tasks to $n$ workers --> Hungarian algorithm or bitmask DP.

"Choose $k$ items with maximum/minimum weight." --> Sort + greedy (take best $k$). If there are dependencies, think DP or matroid intersection. Example: Maximum sum of $k$ elements --> sort descending, take first $k$.

---

Geometry & Coordinates

"Closest pair / nearest neighbor." --> Divide and conquer or sweep line. $O(n\log n)$. Example: Closest pair of points in 2D --> classic divide-and-conquer.

"Convex hull of points." --> Andrew's monotone chain or Graham scan. Example: Smallest enclosing fence --> convex hull.

"Maximum/minimum dot product with a direction." --> Convex hull trick (optimization over linear functions). Example: DP where transition is $dp[j]+b[j]\cdot a[i]$ --> convex hull trick.

---

Meta-Patterns

"Problem looks like X but constraint is too large." --> The intended solution probably uses a different technique than the obvious one. Look for: sqrt decomposition, offline processing, or a smarter state representation.

"Problem gives unusual constraints like $n\le 20$." --> Bitmask DP ($2^{20}\approx {10}^6$, fast enough). Or brute-force with pruning.

"$n\le 500$ and involves pairs." --> $O(n^3)$ algorithms are likely: Floyd-Warshall, matrix multiplication, Gaussian elimination.

"$n\le {10}^5$ and needs something per element." --> $O(n\log n)$ or $O(n\sqrt{n})$: segment tree, BIT, sorting + sweep, Mo's algorithm.

"Values up to ${10}^9$ but only $n\le {10}^5$ distinct values." --> Coordinate compression, then use value-indexed data structures.

---

How to Use This Catalog

Don't memorize it. Read through it once to plant seeds. When you're stuck on a problem:

1. Identify the trigger phrase in the problem statement.
2. Look up the corresponding reduction in this catalog.
3. Check if the reduction actually applies -- verify monotonicity for binary search, DAG structure for topo sort, associativity for segment trees.
4. Implement the reduction, not just the algorithm.

The gap between a 1400-rated and a 1900-rated programmer isn't algorithmic knowledge -- it's pattern recognition speed. This catalog is a head start.

Quick Reference Table

Trigger	Technique	Key Check
"Minimize the maximum"	Binary search on answer	Feasibility is monotonic
"Count the number of ways"	DP	State = position + constraints
"Shortest path"	BFS/Dijkstra/Bellman-Ford	Edge weight structure
"Connected components"	DSU / BFS	Static vs dynamic
"Range query + point update"	Segment tree / BIT	Associative combine
"Matching/assignment"	Bipartite matching / flow	Bipartiteness
"Game, two players, optimal"	Sprague-Grundy / minimax	Impartial vs partisan
"Subsequence"	DP on sequence	Monotonicity for greedy
"Permutation pattern"	Inversion counting / BIT	Sortedness measure

---

Common Mistakes in Choosing

• Matching the trigger without checking preconditions. "Minimize the maximum" suggests binary search -- but only if feasibility is monotonic. Always verify the structural requirement, not just the phrase.
• Stopping at the first matching trigger. A problem may match multiple triggers. "Count pairs with sum = k in a range" triggers both "counting pairs" (hash map) and "range queries" (data structure). Read all triggers before committing.
• Using this catalog as a substitute for understanding. The catalog generates hypotheses. You still need to verify the hypothesis fits, design the state/graph/check, and implement correctly. Pattern recognition without understanding leads to wrong approaches that "feel right."
• Ignoring constraint-based filtering. A trigger might suggest segment tree, but if n <= 20, bitmask DP is more likely. Always cross-reference triggers with the constraint table.
• Applying graph reductions to non-graph problems. "Connected components changing over time" triggers DSU -- but only if the changes are additions. If edges are deleted, you need offline reversal. The trigger tells you where to look, not what to do.

---

Cross-References

• Problem Pattern Recognition -- the full constraint + trigger + decision tree reference
• Graph Modeling -- when the problem is secretly a graph
• Binary Search Reductions -- optimization to decision
• DP State Design -- choosing what to remember
• DS Augmentation -- teaching old structures new tricks
• Problem Transformations -- changing the problem, not the algorithm
• Data Structure Selection Guide -- picking the right DS
• DP vs Greedy Guide -- DP or greedy?
• BFS vs DFS Guide -- traversal choice

---

Recap

• Trigger phrases are hypotheses, not answers. They tell you where to look; you still must verify the fit.
• Three-step process: identify trigger, look up reduction, check preconditions.
• Strongest signals: "minimize the maximum" = binary search, "count the number of ways" = DP, "connected components" = DSU, "range queries + updates" = segment tree/BIT.
• Meta-patterns matter: n <= 20 = bitmask, n <= 500 = O(n^3), n <= 10^5 = O(n log n). Constraints filter triggers.
• The gap between 1400 and 1900 is pattern recognition speed, not algorithmic knowledge. This catalog is the training aid.