Two skills that decide ICPC results as much as algorithms: implementing ugly problems cleanly, and writing standard structures correctly the first time.
Implementation techniques
| Situation | Technique |
|---|---|
| simulation | keep the state in one struct; one function step(); assert invariants after each step; detect cycles by hashing states |
| events in time | sort events by (time, type) with a clear tie rule; sweep and maintain a structure |
| grids | direction arrays dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1}; an inside(r, c) helper; pad with a border instead of bounds checks |
| rotations / reflections | write rotate90 once and reuse it; normalize shapes by the minimum over all 8 symmetries |
| coordinates | compress early; half-open intervals everywhere |
| parsing | read tokens with cin; recursive descent for expressions (`expr → term (+ |
| state machines | an enum for states, a transition table, no nested if chains |
| heavy casework | normalize by symmetry first; represent cases as data (a table) rather than code; brute force small inputs and compare |
| dates and times | convert to a single integer (days or seconds since an epoch), compute, convert back |
Implementation reliability
| Habit | Why |
|---|---|
| a tested library: segment tree, lazy segment tree, Fenwick, DSU, Dinic, min-cost flow, LCA, HLD, hashing, geometry primitives | typed from memory or the team notebook, it has no bugs |
| invariants as comments | a loop with a stated invariant (“lo is always bad”) is rarely off by one |
| one convention per problem | 0-indexed, half-open, long long for sums |
| small functions with clear inputs | each can be tested alone |
| read the code once before running it | catches most typos faster than debugging |
| stress test whenever the solution is not obviously correct | random small tests against a brute force catch logic errors in minutes |
Writing standard structures without debugging
| Structure | The usual bug | Guard |
|---|---|---|
| segment tree | wrong size, wrong mid split, forgetting to push lazy tags | size (recursive) or power of two; push at the top of every function |
| Fenwick tree | 0-indexing | shift indices by one at the interface |
| DSU | union without find | always a = find(a), b = find(b) first |
| Dinic | missing reverse edges, level graph not reset | add edges in pairs; reset level and it per phase |
| Dijkstra | processing stale queue entries | if (d > dist[u]) continue; |
| geometry | precision, collinear cases | integers where possible; handle collinear explicitly |
| DP | wrong base case or iteration order | write the recurrence and order on paper; test tiny inputs by brute force |
| graphs | 0/1-indexed vertices, multi-edges, disconnected graphs | read the input format twice |
See also Debugging and Stress Testing, 🐬 Before Contest, 🐬 Snippets.