Concepts9
Complexity Analysis Quick Reference
Use an operation budget of about 10^8 simple operations per second on typical online judges; always multiply by the time limit and number of test files if known.
Debugging Strategies for CP
Systematic debugging beats guesswork: always re-read the statement, re-check constraints, and verify the output format before touching code.
Small-to-Large Principle
Small-to-large means always merge the smaller container into the larger one to keep total work low.
Permutations and Combinations
Permutations count ordered selections, while combinations count unordered selections.
Fast Exponentiation
Fast exponentiation (binary exponentiation) computes a^n using repeated squaring in O(log n) multiplications.
Breadth-First Search (BFS)
Breadth-First Search (BFS) explores a graph level by level, visiting all vertices at distance d from the source before any at distance d+1.
0-1 BFS
0-1 BFS is a shortest path algorithm specialized for graphs whose edge weights are only 0 or 1.
Prefix Sum and Difference Array
Prefix sums precompute running totals so any range sum [l, r] can be answered in O(1) time as prefix[r] - prefix[l-1].
Sorting Algorithms
Sorting arranges items into a chosen order so that searching, grouping, and further algorithms become faster and simpler.