Problem Pattern Recognition

Constraint → technique

The constraints are the strongest hint the setter gives. Read them first.

Constraint	Consider
$n\le 10$	brute force, all permutations, backtracking
$n\le 20$	bitmask DP $O(2^{n}n)$
$n\le 40$	meet in the middle $O(2^{n/2})$
$n\le 100$	$O(n^4)$, or flow
$n\le 500$	$O(n^3)$ — Floyd-Warshall, interval DP, matrix ops
$n\le 5000$	$O(n^2)$ DP
$n\le 10^5$	$O(n\sqrt{n})$ — Mo’s, sqrt decomposition
$n\le 2\cdot 10^5$	$O(n\log n)$ — sorting, segment tree, Dijkstra
$n\le 10^6$	$O(n)$ or $O(n\log n)$ with a small constant
$n\le 10^7$	$O(n)$, careful I/O
$n\le 10^{18}$	math, binary exponentiation, matrix power, digit DP
values $\le 10^6$	sieve, frequency array, smallest prime factor
values $\le 10^{18}$	Miller-Rabin, Pollard’s rho
two small parameters ($n$ big, $k\le 15$)	FPT — exponential in $k$
Sum of $n$ over all tests $\le X$	the per-test complexity may depend on that $n$

Phrase → tool

The statement says	Likely tool
”minimise the maximum” / “maximise the minimum”	binary search the answer
”number of subarrays with…“	prefix sums + hash map, or two pointers
”range update / range query”	difference array, BIT, lazy segtree
”connect / merge components”	DSU
”shortest path, unweighted”	BFS
”weights are 0 or 1”	0-1 BFS
”non-negative weights”	Dijkstra
”negative weights”	Bellman-Ford
”dependencies / prerequisites”	topological sort + DAG DP
”tree path queries”	LCA, HLD
”subtree queries”	Euler tour + BIT
”count paths in a tree”	centroid decomposition
”palindromic substrings”	Manacher, Eertree, hashing
”many patterns at once”	Aho-Corasick
”distinct substrings / substring order”	suffix automaton, suffix array
”choose $k$ from $n$, mod a prime”	factorials + inverse factorials
”$n$ huge, prime small”	Lucas
”system of congruences”	CRT
”maximum XOR of a subset”	linear basis
”maximum XOR with an element”	binary trie
”convolution / count pairs summing to”	FFT / NTT
”two choices, pairwise conflicts”	2-SAT
”assign A to B optimally”	matching, Hungarian, MCMF
”select items, some require others”	project selection / min cut
”both play optimally”	game theory, Grundy
”expected value”	linearity of expectation
”count with digit constraints”	digit DP
”queries known in advance”	go offline

The diagnostic questions

1. What is $n$? It picks the complexity class.
2. What is being asked — a count, a maximum, an existence, a construction?
3. Is there structure? A tree, a DAG, bipartite, an interval, planar, a grid.
4. Are the queries offline? If so, sorting them is free.
5. Is the objective minimax or maximin? → binary search.
6. Is it NP-hard? → check the constraints for the intended exponential.
7. Does it decompose into independent parts? → solve separately and combine.
8. What would brute force be? Then look for what to speed up.

Reformulations worth trying

Original	Try instead
Choosing a subset	a flow / cut, or a DP over a sorted order
A hard constraint	binary search on it, or Lagrangian relaxation (Aliens trick)
Maximise a ratio	binary search $\lambda$, test $\sum (a-\lambda b)\ge 0$
Count configurations	count the contribution of each element instead
A condition on all pairs	sort, then it becomes a condition on neighbours
A grid	an implicit graph
A sequence of operations	a graph on states
”At least one of each”	inclusion-exclusion
Reachability with cycles	condense the SCCs
Something about all subarrays	contribution of each element as min/max (monotonic stack)

When stuck

1. Solve $n\le 5$ by hand or brute force; look at the answers.
2. Try the reverse: process from the end, or think about what the answer cannot be.
3. Look for an invariant or a parity obstruction.
4. Consider the complement, or the dual.
5. Ask what a slightly simpler version would need — then add the missing piece.
6. Re-read the statement. The unused constraint is usually the key.

See also: Complexity Cheatsheet · CP Workflow · Graph Modelling Patterns