i. Attacking a Problem

A working toolkit for hard problems: what to look at, which reformulations to try, and how to turn a statement into a known model. Constraint sizes are in Complexity.

The diagnostic questions

1. What does brute force enumerate? That is the object you are optimising over. Which part of the enumeration is redundant?
2. What is the answer’s type? Count, optimum, existence, construction, or $k$-th object. Each has its own toolset (DP or combinatorics, greedy or flow, invariants, constructions, or digit/order-statistic search).
3. Is there structure? Sorted, monotone, convex, tree, DAG, bipartite, planar, interval, permutation, grid, functional graph.
4. Is there independence? Bits, primes, connected components, coordinates, or rows and columns that can be solved separately.
5. Are the queries offline? Then you can sort them, reverse time, divide and conquer, or use Mo’s algorithm.
6. Is it minimax or maximin? Binary search the answer.
7. Is the general version NP-hard? Then some constraint is small. Find it: it’s the exponent or the DP dimension.
8. What does an optimal solution look like? Prove structure lemmas: “WLOG the chosen elements are contiguous after sorting”, “at most one item is partially used”, “some optimal path uses at most $k$ turns”, “the answer is one of $O(n)$ candidates”.

Statement phrase to tool

The statement says	Try
minimise the maximum / maximise the minimum	binary search the answer
maximise a ratio $\sum a/\sum b$	binary search $\lambda$, test $\max \sum (a-\lambda b)\ge 0$ (Dinkelbach converges faster)
number of subarrays with property	prefix sums + hashing, two pointers, contribution with a monotonic stack
sum over all subarrays/pairs/subsets of $f$	contribution technique
exactly $k$ / at least one of each	inclusion-exclusion, Möbius over subsets
choose exactly $k$ things, cost convex in $k$	Aliens trick
range update / range query	difference arrays, BIT, lazy segment tree
connect / merge / “are $u,v$ together”	DSU; offline deletions $\to$ reverse time or segment tree on time
shortest path, weights 0/1 / small integers / non-negative / negative	0-1 BFS / Dial / Dijkstra / Bellman-Ford, Johnson
$x_j-x_i\le c$	difference constraints $\to$ shortest paths
dependencies, prerequisites	topological sort, DAG DP
two choices per item, pairwise conflicts	2-SAT
pick a closed set (taking $x$ forces $y$)	max closure via min cut
assign A to B	matching, Hungarian, min-cost flow
disjoint paths, capacities, “each used at most $c$ times”	max flow, vertex splitting
tree path / subtree queries	LCA, Euler tour, HLD, centroid decomposition
count pairs of tree vertices with distance property	centroid decomposition, small-to-large
many patterns in a text	Aho-Corasick; distinct substrings $\to$ suffix automaton or array
palindromes	Manacher, eertree, palindromic series
$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}p$, $n$ huge, $p$ small	Lucas, Granville for prime powers
count pairs with $a_i+a_j=s$ for all $s$	FFT/NTT
$\mathrm{xor}$/$\mathrm{and}$/$\mathrm{or}$ over subsets	FWHT, SOS DP, linear basis
linear recurrence, huge $n$	matrix power, Kitamasa, Bostan-Mori, Berlekamp-Massey
both players play optimally	Sprague-Grundy, minimax DP, strategy stealing, pairing
expected value	linearity of expectation, indicator variables
numbers in $[L,R]$ with a digit property	digit DP
online, with forced decoding (^ lastans)	persistent structures, online sqrt
$n\le 10^5$ and a weird operation	sqrt decomposition, bitset, small/large threshold

Constraint to technique

The constraints are the strongest hint the setter gives — read them first. (See also Complexity and Analysis and Before Contest for the same lookup in other shapes.)

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$, not the single-test bound

Reformulations

Original	Try
a condition on all pairs	sort first. It often becomes a condition on adjacent elements
choose a subset	sort by a key and DP over the order (exchange argument decides the key)
a hard constraint	binary search on it, or relax it with a Lagrange multiplier
a process of operations	find what is invariant, and characterise reachable states
operations applied forwards branch a lot	work backwards
deletions	reverse time and turn them into insertions
Manhattan distance	rotate: $(x,y)\mapsto (x+y,x-y)$ turns it into Chebyshev distance, so axes become independent
median $\ge x$	map to $\pm 1$ by comparing with $x$, then require sum $\ge 0$; binary search $x$
average $\ge x$	subtract $x$, then require sum $\ge 0$
strictly increasing	$b_i=a_i-i$ makes it non-decreasing (proof below)
products	logarithms, or prime exponent vectors
XOR along tree paths	root prefix XORs: $p_u\oplus p_v$
bracket sequences	$\pm 1$ prefix sums: never negative, end at 0 (proof below)
tree paths and subtrees	Euler tour turns subtrees into ranges, HLD turns paths into $O(\log n)$ ranges
interval containment or overlap	points in the plane $(l,r)$ and dominance counting
cyclic arrays	double the array, or fix the cut point
counting configurations up to rotation	Burnside
the answer is small	iterate over the answer and check feasibility
answer is a sum of independent parts	solve each bit, prime or component separately
cost depends on (number of items) and (their sum)	swap the DP’s value and dimension
maximum over $k$ of something convex	ternary search or a monotone pointer over $k$

Proof: the two reformulation identities above

Strictly increasing $\to$ non-decreasing. $a_i<a_{i+1}$ for all $i$ (integers) is equivalent to $a_{i+1}-a_i\ge 1$, i.e. $a_{i+1}-(i+1)\ge a_i-i$, i.e. $b_{i+1}\ge b_i$ with $b_i=a_i-i$ — exactly non-decreasing. This turns “distinct/strictly increasing” combinatorics (e.g. choosing a strictly increasing sequence) into ordinary “choose a non-decreasing / multiset” combinatorics, a standard bijection (stars and bars after the shift).
Bracket sequences $\leftrightarrow$ $\pm 1$ walks. Map ( to $+1$ and ) to $-1$ and take prefix sums $s_0=0,s_1,\dots ,s_n$. A sequence is a valid balanced bracket sequence iff every prefix has at least as many ( as ) (so every suffix can still be closed) and the total count matches — exactly $s_i\ge 0$ for all $i$ and $s_n=0$. Conversely any $\pm 1$ sequence with these two properties decodes back to a valid bracket sequence by definition of the encoding, so the correspondence is a bijection, letting bracket-sequence problems be solved as constrained lattice-path problems (and vice versa, e.g. via the cycle lemma for counting). $■$

Modeling

Signal	Model
minimum moves between configurations	BFS on the state graph
moves with costs	Dijkstra on the state graph, possibly with potentials
choices with overlapping subproblems	DP over (position, small extra state)
conflicts between two groups	bipartite graph: matching, König, vertex cover
selection with dependencies	min cut (project selection)
“every row and column exactly once”	bipartite perfect matching / permutation
grid with domino or rook placements	rows and columns or black and white cells as the two sides
DAG path cover	$n-$ maximum matching on the split graph
equivalences, merging	DSU, possibly with parity or weights
order constraints	DAG, or difference constraints if they’re numeric

Flow-modeling specifics, once “Modeling” above has pointed at flow:

• Source $\to$ left side with capacity = supply, right side $\to$ sink with capacity = demand.
• Vertex capacities: split $v$ into $v_{in}\to v_{out}$.
• Lower bounds: circulation with demands.
• Costs: min cost flow. Convex costs mean parallel edges with increasing costs.
• Min cut = minimum “price” to separate. Infinite edges encode “cannot cut here”.

State graph: a state is everything that determines the future, such as (cell, collected keys as a mask, direction, time mod $k$, fuel). Count states times transitions before coding, then shrink by dropping irrelevant information or exploiting symmetry.

DP state design: describe $dp[\text{state}]$ in words; the state must determine the future without the history; the transition is the last (or first) decision. When the state space is too big, look for dominance (keep a Pareto front), monotonicity of the optimal choice (DP optimisations), or swap a dimension with the value. More in DP Foundations.

Algorithmic paradigms

A paradigm is a reusable high-level strategy, distinct from any one algorithm (Quicksort is an algorithm; divide and conquer is the paradigm behind it). Paradigms are not mutually exclusive — Kruskal’s MST is greedy + DSU; A* is state-space search + a heuristic. Decide by asking: does the problem have optimal substructure? Do subproblems overlap or stay independent? Does a locally optimal choice provably compose into a globally optimal one? Is it NP-hard (then exact-small/approximate/heuristic)? Online or offline? In memory or streamed?

Exhaustive search

Paradigm	Idea and mechanism	Iconic problems	When / trade-off
Brute force	enumerate every candidate, test each; correctness from exhaustiveness alone	correctness baseline for stress tests	small $n$ only; trivial to implement, scales catastrophically
Backtracking	DFS over partial solutions, prune a branch the moment it’s invalid	N-Queens, Sudoku, graph colouring	real pruning (ordering, constraint propagation) often turns exponential into fast in practice
Branch and bound	backtracking + a bound on the best achievable value from a partial solution, prune anything that can’t beat the incumbent	TSP exact, 0/1 knapsack exact	worst case exponential; a weak bound degenerates to brute force
Meet in the middle	split input in half, enumerate each half, combine (sort + binary search / two pointers)	subset sum $n\le 40$, 4-SUM	needs the two halves to combine independently; extra space for the enumerated half
State-space search	model as states/transitions, search start $\to$ goal	pathfinding, 15-puzzle, Rubik’s	state explosion is the enemy; A*/IDDFS/bidirectional mitigate it
Bitmask enumeration	subsets/states as integers, __builtin_popcount, submask iteration (sub-1)&mask in $O(3^n)$ total	Held-Karp TSP, SOS DP, assignment	exponential by construction; the point is a fast constant where “better” asymptotics are overkill at this $n$

Divide-based

Paradigm	Idea and mechanism	Iconic problems	When / trade-off
Divide and conquer	split into independent subproblems, recurse, combine; $T(n)=aT(n/b)+f(n)$, master theorem	merge sort, closest pair, Karatsuba, FFT	subproblems must genuinely not share state, else redundant recomputation
Decrease and conquer	reduce to one smaller instance (not several)	binary search, insertion sort, Euclid’s algorithm	simpler recurrence, less parallelizable (one active thread)
Transform and conquer	change representation/domain so the transformed problem is easier	heapify, coordinate compression, Gaussian elimination	transform cost must be amortized by the savings; must be answer-preserving

Optimization

Paradigm	Idea and mechanism	Iconic problems	When / trade-off
Greedy	locally optimal choice every step, correctness via exchange argument or matroid structure	activity selection, Huffman, Kruskal/Prim, Dijkstra, fractional knapsack	fast when it works, silently wrong when the greedy-choice property fails (0/1 knapsack)
Matroid-based greedy	greedy is provably optimal exactly when the structure is a matroid	MST (graphic matroid), max weight forest, deadline scheduling (transversal matroid)	recognising matroid structure is itself nontrivial
Dynamic programming	optimal substructure + overlapping subproblems, solve each state once	knapsack, LCS, edit distance, digit/bitmask/tree DP	state design is the crux; space often reducible to the last 1-2 layers
Memoization	the top-down form of DP: natural recursion + cache	Fibonacci, tree DP	good when only a sparse fraction of states are reached, or bottom-up order is awkward
Network flow	model as capacitated flow, exploit max-flow/min-cut	bipartite matching, project selection, segmentation, disjoint paths	the hard part is almost always the modeling, not running Dinic’s

Approximate and probabilistic

Paradigm	Idea and mechanism	Iconic problems	When / trade-off
Randomized	random choices beat adversarial inputs or simplify design; Las Vegas (always correct, random time) vs. Monte Carlo (bounded time, random correctness)	randomized quicksort, Miller-Rabin, Karger’s min-cut	error must be quantified/amplified; see Complexity Theory for BPP/RP/ZPP
Approximation	trade guaranteed optimality for a provable ratio $\alpha$ in poly time	vertex cover (2-approx), metric TSP (3/2, Christofides), set cover ($O(\log n)$), max cut (0.878, Goemans-Williamson)	designing a good ratio is often as hard as the problem itself; see Complexity Theory for PTAS/FPTAS and inapproximability
Heuristic / metaheuristic	find good-not-necessarily-optimal solutions fast, no guarantees: hill climbing, simulated annealing, genetic algorithms, tabu search	large TSP, VLSI placement, hyperparameter tuning	tuning (cooling schedule, population, mutation rate) is itself an engineering problem
Parameterized (FPT)	isolate parameter $k$, solve in $f(k)\cdot n^{O(1)}$: kernelization, bounded search trees, colour-coding, treewidth DP	vertex cover $O(1.2738^k+kn)$, $k$-path, feedback vertex set	not every NP-hard problem is FPT (W-hierarchy); $f(k)$ can be astronomical even with a “polynomial” exponent

Query and range

Paradigm	Idea and mechanism	Iconic problems	When / trade-off
Search	narrow a candidate range repeatedly: binary (sorted), ternary (unimodal), interpolation (uniform, $O(\log \log n)$ expected)	find an element, convex minimum, “smallest $x$ with predicate($x$)“	needs sortedness or unimodality
Sliding window / two pointers	maintain a window, adjust boundaries incrementally instead of recomputing	longest substring without repeats, min window substring	needs the monotonicity assumption (shrinking never needs to re-grow past where it was)
Sqrt decomposition / Mo’s	block the array ($O(\sqrt{n})$ per op) or block the query set (sort by block, amortized $O(n\sqrt{q})$ total)	range sum/min with updates, offline distinct-in-range, range mode	$O(\sqrt{n})$ loses to $O(\log n)$ structures where those apply, but Mo’s handles query types (distinct count) a segment tree can’t; strictly offline
Persistent structures	keep every past version queryable (partial) or even editable (full), via path copying: $O(\log n)$ new nodes per update	$k$-th smallest in a range, version-controlled arrays, “value at time $t$“	extra $O(\log n)$ space per update; harder to implement correctly
Amortized / incremental	bound the total cost of a sequence, not each operation: aggregate analysis, accounting method, potential method	dynamic array push_back, DSU with compression, splay trees	total-cost guarantee, not a per-operation one — unsuitable for hard real-time constraints

Data-scale

Paradigm	Idea and mechanism	Iconic problems	When / trade-off
Online	commit to each decision immediately, no future knowledge; measured by competitive ratio vs. optimal offline	LRU/FIFO paging, online bipartite matching, ski rental	optimality fundamentally capped by lack of foresight
Streaming	one pass, memory far smaller than the stream: reservoir sampling, Count-Min, HyperLogLog, Bloom filters	heavy hitters, distinct-IP counting	approximate with quantified error; data can’t be revisited — see Complexity Theory for communication complexity
Sublinear / property testing	decide “has property” vs. “$\epsilon$-far from it” examining a sublinear (sometimes $O(1)$) fraction of input	is this list sorted?, is this graph bipartite?	no guarantee near the boundary; needs a well-defined distance metric
Cache-oblivious / external memory	efficient under a two-level memory hierarchy, either by counting block transfers explicitly or (more elegantly) with no knowledge of block size at all	external merge sort, cache-oblivious B-trees	external-memory needs hardware tuning ($B,M$); cache-oblivious avoids that but is harder to design
Distributed / parallel	split computation across cores (parallel) or machines (distributed): SIMD/GPU, task-parallel, MapReduce, consensus protocols	parallel prefix sum, distributed shortest paths, large-scale ML training	Amdahl’s law bounds speedup by the sequential fraction; communication/load-balancing/fault-tolerance add complexity

Small cases and OEIS

For constructive, counting and ad hoc problems, brute force $n=\mathrm{1..8}$ and look at the output.

• Print the solutions themselves, not just yes/no: the structure of the construction (alternating, mirrored, extending the $n-1$ case, using the bits of $i$) is usually visible right away.
• For integer sequences, compute 8-12 terms and search OEIS. It’s allowed, fast, and often the intended path.
• For a polynomial in $n$, interpolate. For a linear recurrence, run Berlekamp-Massey on $2k$ terms. For periodicity, look at the answers mod small $k$ and at differences.
• Verify every conjecture against the brute force on a wider range before submitting — ten thousand random small tests take seconds and catch nearly every wrong conjecture (Debugging and Stress Testing). Skipping this step is where wrong answers come from.

Sequence	Probably
1, 2, 4, 8, 16	$2^n$
1, 1, 2, 3, 5, 8	Fibonacci
1, 1, 2, 5, 14, 42	Catalan
1, 2, 5, 15, 52	Bell
1, 3, 13, 75, 541	ordered Bell (Fubini)
0, 1, 2, 9, 44, 265	derangements
1, 1, 3, 15, 105	double factorials $(2n-1)!!$
1, 1, 2, 4, 9, 21, 51	Motzkin
1, 2, 6, 22, 90	large Schröder
1, 1, 1, 2, 3, 6, 11, 23	Wedderburn-Etherington (unlabelled binary trees)
1, 1, 2, 4, 9, 20, 48	unlabelled rooted trees
1, 1, 2, 3, 5, 7, 11, 15, 22	partitions $p(n)$
$n^{n-2}$: 1, 1, 3, 16, 125	Cayley, labelled trees

Working backwards

Start from the final state and undo operations. This helps when the forward process branches but the backward one is forced.

• The last operation is visible: the last stamp is fully visible, the last merge involves the maximum, the last move in a game reaches a terminal position (retrograde analysis).
• Euclid-like moves $(a,b)\to (a+b,b)$ reverse to repeated subtraction, which is the Euclidean algorithm and takes $O(\log )$ with division.
• Reaching $t$ from $s$ with $\times 2$ and $+1$: backwards, halve when even, otherwise subtract.
• Edge deletions with connectivity queries: reverse time so deletions become DSU unions.
• If an operation loses information (integer division, max), going backwards branches. Then check the backward greedy step is really forced.

Case analysis and normalisation

• Split by size (small $n$ separately by brute force), parity, sign or zero, extremes (all equal, sorted, impossible), relative order, and structure (tree vs has a cycle, connected vs not).
• Normalise to cut cases: WLOG $a\le b$ (swap), the first element is positive (negate), the string starts with 0 (flip), the target is in the first quadrant (reflect), the minimum is 0 (shift).
• Make sure the cases cover everything and agree on their boundaries. Too many cases is a smell: look for a uniform invariant or formula.

Symmetry

• Reverse the array or rotate the grid four times and reuse the same code for each direction.
• Assume $x\le y$, double the count, and fix the diagonal $x=y$ (counted twice).
• In probability, symmetric items are equally likely to be first, last or in any position. Element $i$ is a prefix maximum of a random permutation with probability $1/i$, so the expected number of records is $H_n$.

Proof: the expected number of records is $H_n$

Element at position $i$ (1-indexed) is a “record” (prefix maximum) iff it is the largest among the first $i$ elements. By symmetry, each of those $i$ elements is equally likely to be the largest (every relative order of the first $i$ elements is equally likely in a uniformly random permutation), so $\mathrm{Pr}[\text{record at }i]=1/i$. By linearity of expectation, $\mathbb{E}[\#\text{records}]={\sum }_{i=1}^n\mathrm{Pr}[\text{record at }i]={\sum }_{i=1}^n\frac{1}{i}=H_n$. $■$

• In games, the mirror strategy on a symmetric position wins for the second player if mirrored moves are always legal.
• Counting up to relabelling or rotation: Burnside and Pólya (Burnside).

Relaxation, bounds and tightness

Drop a constraint, solve the easier problem, and check or repair.

• Bound and construct: prove a lower bound (each element needs one operation, each move decreases the potential by at most 1, a cut argument), then build a solution meeting it. Many constructive problems are exactly this.
• LP relaxation is integral for totally unimodular systems (bipartite matching, flows, interval matrices), so the LP dual gives min-max theorems: König, max-flow/min-cut, Dilworth.
• Lagrangian relaxation: move “exactly $k$” into the cost with a penalty $\lambda$ (Aliens trick).
• Allow illegal moves (negative counts, teleports), find the easy answer, then prove it’s achievable.

When stuck

1. Re-read the statement and list every constraint. The unused one is usually the key.
2. Solve tiny cases by hand or by brute force.
3. Reverse the process, complement the count, or dualise the optimisation.
4. Look for an invariant or a parity obstruction (Invariants).
5. Fix one variable (the maximum, the number of groups, the first position, the answer’s bit) and optimise the rest.
6. Solve the version with no updates, one query, a path instead of a tree, or distinct values, then add the missing piece.
7. Think about a square-root threshold: few heavy objects plus many light ones, each easy separately.