Concepts18
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.
Small-to-Large Principle
Small-to-large means always merge the smaller container into the larger one to keep total work low.
Double Counting
Double counting is the strategy of counting the same quantity in two different ways to derive an equality or an efficient algorithm.
Think Backwards (Reverse Thinking)
Think Backwards is a problem‑solving pattern where you reverse time or direction so hard deletions become easy insertions and the final state becomes the starting point.
Invariant Maintenance
An invariant is a property you promise to keep true throughout an algorithm, and it is the anchor of both design and correctness proofs.
Amortized Analysis
Amortized analysis measures the average cost per operation over a worst-case sequence, not over random inputs.
Sqrt Decomposition on Queries
Sqrt decomposition on queries (time blocking) processes Q operations in blocks of size about \(\sqrt{Q}\) to balance per-query overhead and rebuild cost.
Small-to-Large Merging
Small-to-large merging is a technique where you always merge the smaller container into the larger one to guarantee low total work.
Minimum Rotation
The minimum rotation of a string is the lexicographically smallest string you can get by cutting it at some position and swapping the two parts.
Convex Hull Trick (CHT)
The Convex Hull Trick (CHT) speeds up dynamic programs where each state is a minimum over linear functions, such as dp[i] = min_j (dp[j] + b[j] × a[i]).
Sliding Window
Sliding window is a technique that moves a contiguous segment (window) across an array or string while maintaining some running information like sum, count, or max.
Palindromic Tree (Eertree)
A Palindromic Tree (Eertree) stores every distinct palindromic substring of a string as a node and can be built online in linear time.