🐬 Before Contest

Everything contest-only in one place: the pre/during/post-contest checklist, the statement-pattern lookup, common mistakes, and small tricks. Nothing here is a technique on its own — each row points at the note that actually explains it.

Checklist

Before the contest

• Template compiles; fast I/O; debug macro prints to stderr only (C++ for CP).
• Stress-test script ready: brute force, generator, checker (Debugging).
• Team: reference document printed, roles agreed (Contest Strategy).

Reading

• Read every problem’s statement and constraints; note the easiest by the scoreboard.
• For each problem: input limits $\to$ target complexity (see Techniques by Pattern below).
• Re-read samples; solve one sample by hand before designing.

Before coding

• I can state the algorithm in two sentences and its complexity fits.
• I know why it is correct (or I have a brute force to stress it).
• Edge cases listed: $n=1$, empty, all equal, max values, negatives, disconnected.

Before submitting

• long long where needed; mod applied everywhere.
• Multi-test: every global reset.
• Array sizes and indices checked; no debug output on stdout.
• Ran samples and a max test for time.
• Output format (spaces, newlines, YES/Yes, precision).

After a wrong answer

• Re-read the statement; check every item above, and the Common Mistakes table below.
• Stress test against the brute force on small random inputs.
• Explain the solution to a teammate (or out loud); check the proof.

After the contest

• Upsolve every problem you could almost solve; write the missing idea down (Problem Set).

Techniques by pattern

Statement pattern $\to$ first technique to try. Constraints decide as much as wording: see Complexity and Analysis for “what fits in one second”.

By wording

The statement says	Try first	Note
minimise the maximum / maximise the minimum	binary search on the answer	Binary Search
minimum number of operations, answer looks tiny	prove the answer is $\le 2$ or $3$, check the small cases	Small Answers
”is it possible to turn A into B”	invariants, canonical forms	Reachability
output any valid object or $-1$	necessary conditions, then a construction	Constructive
sum over all subarrays / pairs / subsets	contribution of each element	Contribution
count objects avoiding a property	complement, inclusion–exclusion	Inclusion–Exclusion
expected value	linearity of expectation, indicators	Probability
nearest greater / smaller, spans, histograms	monotonic stack	Monotonic Stack
longest / shortest subarray with a monotone condition	two pointers	Two Pointers
range queries, no updates	prefix sums, sparse table	Sparse Table
range queries with updates	Fenwick or segment tree (lazy for range updates)	Segment Tree
many offline range queries, hard to merge	Mo’s algorithm	Mo
connectivity under edge additions	DSU	DSU
path queries on a tree	LCA, HLD, Euler tour	HLD
count paths with a property in a tree	centroid decomposition, small to large	Centroid
shortest path, weights 0/1 or states	0-1 BFS, Dijkstra on a state graph	Shortest Paths
choose a subset, pairwise conflicts, bipartite	matching, min vertex cover (König)	Bipartite Matching
choose items with dependencies, profits and costs	project selection = min cut	Flow Modeling
boolean constraints on pairs	2-SAT	2-SAT
xor of subsets, max xor	linear basis over GF(2)	XOR Basis
count numbers in $[L,R]$ with a digit property	digit DP	Digit DP
$n\le 20$, subsets	bitmask DP, SOS DP, meet in the middle	Bitmask DP
huge $n$, linear recurrence	matrix power, Berlekamp–Massey	Matrix Power DP
$d{p}_i={\min }_j(a_j{x}_i+b_j)$	convex hull trick, Li Chao	CHT
”exactly $k$ items” on a convex cost	Aliens trick	Aliens
$\sum f(\lfloor n/i\rfloor )$, $n\le 10^{12}$	harmonic lemma / floor blocks	Floor Sums
polynomial products, counting by size	FFT / NTT	FFT
impartial game	Sprague–Grundy	Sprague–Grundy
string equality checks, many substrings	hashing, prefix function, suffix array	Hashing

By constraints

Constraint	Typical complexity	Typical tools
$n\le 10$	$O(n!)$	permutations, backtracking
$n\le 20$	$O(2^{n}n)$	bitmask DP
$n\le 40$	$O(2^{n/2})$	meet in the middle
$n\le 500$	$O(n^3)$	Floyd–Warshall, interval DP
$n\le 5000$	$O(n^2)$	quadratic DP, $O(n^2/64)$ bitsets for $10^4$–$10^5$
$n\le 2\cdot 10^5$	$O(n\log n)$, $O(n\sqrt{n})$	sorting, segment trees, Mo
$n\le 10^7$	$O(n)$	sieves, linear scans
$n\le 10^{12}$	$O(\sqrt{n})$, $O(n^{2/3})$	divisors, floor blocks, Du / min_25 sieves
$n\le 10^{18}$	$O(\log n)$	matrix power, binary lifting, closed forms

Common mistakes

One line per mistake, with the fix. Full checklists: Debugging and Stress Testing, C++ for CP.

Mistake	Symptom	Fix
int overflow in products or sums	WA on large tests	long long for anything that can exceed $2\cdot 10^9$; 1LL * before products
product of two long long mod $m$ overflows	WA for $m>3\cdot 10^9$	__int128 or Montgomery
negative %	negative residues	((a % m) + m) % m
integer division of negatives rounds toward zero	off by one for negatives	floorDiv / ceilDiv helpers
sz(v) - 1 with unsigned size()	huge loop when empty	cast to int (sz macro)
not resetting globals between test cases	WA on test 2	clear exactly the used part, per test
memset on every test	TLE with many tests	reset only $O(n)$ entries
endl in loops	TLE	'\n'
recursion depth $10^5$–$10^6$	RE (stack overflow)	iterative DFS, or ulimit -s locally only
map / set where a vector suffices	TLE	sort + lower_bound, arrays
unordered_map with adversarial keys	TLE (anti-hash tests)	splitmix64 custom hash
comparator not a strict weak order (<=)	RE / WA in sort	always <
floating equality	WA on precision tests	integers, or compare with $\epsilon$
binary search off by one	infinite loop or wrong bound	write the invariant: lo is always bad, hi always good
1-indexed vs 0-indexed mixing	WA on borders	choose one convention per problem
forgetting $n=1$, empty input, all equal	WA on edge tests	test the edges before submitting
graph not connected, multi-edges, self-loops	WA on hidden tests	handle each explicitly
wrong modulus or forgetting a final mod	WA	one const int MOD and a Mint type
array too small by one or by a factor of 2 (segment tree)	RE / WA	4n for recursive segment trees; N + 5 padding
reading the problem too fast	solving the wrong problem	re-read the statement and the samples before coding
debug output left in	WA / TLE	print debug to stderr with a macro

Tricks list

Small tricks that turn up everywhere, each with its use and the note that explains it.

Trick	Use	Note
rotate coordinates $(x,y)\to (x+y,x-y)$	Manhattan distance becomes Chebyshev (max of two)	Attacking a Problem
prefix sums / difference arrays	$O(1)$ range sums, $O(1)$ range additions offline	Prefix Sums
prefix xor	subarray xor = xor of two prefixes	Prefix Sums
sort + two pointers	pairs with a sum condition in $O(n\log n)$	Two Pointers
coordinate compression	values up to $10^9$ into indices	Sorting
contribution technique	sum over all subarrays as a sum over elements	Contribution
small to large	merge sets in $O(n\log n)$ total	Small to Large
sqrt split by frequency / degree	heavy and light elements handled differently	Sqrt Decomposition
binary lifting	$k$-th ancestor, jumps in functional graphs	LCA
reverse time	deletions become insertions (DSU)	Offline Techniques
parallel binary search	many binary searches over the same updates	Parallel Binary Search
Kruskal reconstruction tree	queries “max edge on the path” / thresholds	KRT
Euler tour flattening	subtree queries become range queries	Euler Tour
submask enumeration s = (s - 1) & m	$O(3^n)$ over all masks	Submasks
bitset shift-or	subset sums and boolean DP in $/64$	Word-Level Parallelism
random hashing of sets (xor of random 64-bit keys)	compare multisets / subarrays in $O(1)$	Randomized Algorithms
doubling the array	cyclic problems on a line	Classic Array Problems
sentinel values	remove border checks	C++ for CP
$\lfloor n/i\rfloor$ takes $O(\sqrt{n})$ values	sums over divisors and quotients	Floor Sums
ternary search on a convex function	optimum of unimodal functions	Ternary Search
slope trick	convex piecewise-linear DP with heaps	Slope Trick
Aliens trick	remove “exactly $k$” by a penalty	Aliens Trick
Chtholly tree (ODT)	range assignment with random data	Chtholly Tree
answer is small	check 0, 1, then the universal bound	Small Answers
meet in the middle	$2^{n/2}$ instead of $2^n$	Meet in the Middle