The Budget Law

A constraint line is not a nuisance — it is the setter telling you which solutions are allowed to exist. The discipline: multiply out the op count before writing any code.

The standard ladder (≈ 10^8 ops per second ceiling; ~3·10^8 is the

"code it now" edge from exam-room experience)

| Constraint | Budget | Families that fit | |---|---|---| | n ≤ 20 (or n ≤ 24) | 2^n–2^n·n | brute force, bitmask DP, meet-in-the-middle above that | | n ≤ 500 | n^3 | Floyd–Warshall, assignment DP, dense graph passes | | n ≤ 5000 | n^2 | pairwise DP, O(n^2) sweeps, LIS bottom-up | | n ≤ 10^5 – 2·10^5 | n log n (or n·√n) | sorting, heaps, segment trees, DSU, Dijkstra | | n ≤ 5·10^6+ | n (tiny constant) | two pointers, sieve, prefix sums, KMP | | value ≤ 10^18 | log(value) | binary search on answer, digit DP, matrix power | | n ≤ 40, subset sums | n/2 · 2^(n/2) | meet in the middle | | q ≤ 10^5, values ≤ 10^5 | (n + q) log | offline sorting + Fenwick sweeps |

Multiplying honestly

O(n·q) with n = q = 2·10^5 is 4·10^10 — a hundred times past the ceiling, not "a bit slow". O(n√n) with n = 10^5 is 3·10^7 — comfortable. O(2^n) with n = 24 is 1.7·10^7 — fine; with n = 30 it is 10^9 — dead. Write the number down; do not eyeball it.

The two-sided error

• Under-budgeting (picking n^2 for n = 2·10^5) = guaranteed TLE on the big test.
• Over-budgeting (inventing an O(n log n) solution for n ≤ 500) = wasted hours and bug surface. When n ≤ 20, brute force IS the intended solution — code it with confidence.

Worked reflex

n ≤ 10^5, q ≤ 10^5, "for each query, the nearest j > i with a[j] > a[i]": budget n log n; shape = per-index nearest-right-greater; families = sorted sweep with a monotonic stack of seen values (process right to left with a stack, or coordinate-compressed Fenwick scanning from the right). Two candidates, both fit — pick the one with less code. That's the whole decision.