| Reading a problem |
- Read a problem's constraints and derive the operation budget they imply
- Identify the edge cases a statement implies but does not list
- Write a solution that reads input and writes output in the format required
|
c++20 |
| Counting the work |
- Derive the complexity of a loop nest and confirm it by doubling the input
- Find the hidden cost in a standard-library call inside a loop
- Recognise when the constant factor rather than the exponent is the problem
|
c++20 |
| Template and fast I/O |
- Measure what C++ stream I/O costs and know when it matters
- Read every input shape a contest uses, including one with no count
- Write a template that does not get in your way
|
c++20 |
| Sorting and comparators |
- Write a comparator that is a valid strict weak ordering
- Choose between sort and stable_sort on evidence
- Compress a large value range into small indices
|
c++20 |
| Binary search |
- Use lower_bound, upper_bound and equal_range correctly
- Write a binary search whose invariant you can state
- Recognise a problem where the answer itself can be searched for
|
c++20 |
| Two pointers |
- Explain why two forward-moving indices give O(n) rather than O(n²)
- Write a variable-size window that maintains a condition
- Recognise the precondition a sliding window needs
|
c++20 |
| Prefix sums |
- Answer range-sum queries in O(1) after an O(n) precomputation
- Get the half-open index convention right, in one and two dimensions
- Apply many range updates in O(1) each with a difference array
- Recognise a sweep as a difference array over sparse coordinates
- Use prefix sums where a sliding window is invalid
|
c++20 |
| Monotonic stacks |
- Recognise the "nearest greater or smaller element" shape in a problem
- State and maintain the invariant a monotonic stack keeps
- Explain why the nested while loop is O(n) in total
- Use previous-smaller and next-smaller spans to count subarrays
- Choose the tie-breaking rule that avoids double counting
|
c++20 |
| Monotonic deques |
- Maintain the maximum of a sliding window in O(1) amortised per step
- State the two reasons an index leaves a monotonic deque
- Compare the deque against a multiset and know what the log factor costs
- Combine two deques to bound a window's spread
- Use a deque over prefix sums where a window is invalid
|
c++20 |
| Hashing and counting |
- Choose between an array, a hash map, an ordered map, and sorting
- Explain why std::unordered_map can degrade to O(n) per operation
- Write a custom hash that resists an anti-hash test
- Use a custom hash or a packed key for pair and tuple keys
- Know what std::multiset's two erase overloads do
|
c++20 |
| Recursion |
- Write a search as choose / explore / un-choose and keep the state consistent
- Prune a search at the moment a partial solution becomes invalid
- Measure the cost of a recursive frame and know your depth budget
- Recognise when overlapping subproblems make memoisation apply
|
c++20 |
| Bitmasks |
- Represent a subset as an integer and enumerate all of them
- Use the standard bit intrinsics instead of hand-rolled loops
- Enumerate every submask of every mask in 3^n rather than 4^n
- Generate distinct permutations and combinations without writing a recursion
|
c++20 |
| Greedy |
- State a greedy algorithm as a choice rule plus a claim
- Test a greedy rule against brute force before trusting it
- Prove a greedy optimal with an exchange argument
- Recognise the problems where greedy is provably wrong
|
c++20 |
| Divide and conquer |
- Recognise the split / solve / combine shape and its recurrence
- Count inversions in O(n log n) by piggy-backing on a merge
- Choose a base-case cutoff by measurement
- Halve an exponent instead of decrementing it
- Know when divide and conquer is the wrong tool
|
c++20 |
| Meet in the middle |
- Recognise the n around 40 constraint as a meet-in-the-middle signal
- Enumerate half the input and combine with sorting or hashing
- Choose between binary search, two pointers, and a hash map for the combine
- Judge when the memory cost makes the technique unavailable
|
c++20 |
| Representing graphs |
- Choose between an adjacency list, a matrix, and an edge list
- Build a compressed adjacency structure in one pass
- [object Object]
- Treat a grid as a graph without materialising it
|
c++20 |
| BFS |
- Write BFS and know why it gives shortest paths in an unweighted graph
- Mark vertices when they are enqueued, and know what it costs not to
- Seed the queue with many sources to get "distance to the nearest"
- Use a deque for 0/1 edge weights instead of a heap
|
c++20 |
| DFS |
- Write DFS iteratively and know when the recursive form will overflow
- Count connected components
- Detect a cycle in a directed graph with three colours
- Find bridges with entry times and low-links
- Use entry/exit intervals as an ancestor test
|
c++20 |
| Topological order |
- Produce a topological order with Kahn's algorithm and with DFS
- Detect a cycle from the length of Kahn's output
- Get the lexicographically smallest order with a heap
- Write a DP over a DAG in topological order
|
c++20 |
| Union-Find |
- Implement find with path compression and union by size
- Measure what each optimisation is worth
- Maintain component counts and sizes as edges arrive
- Answer deletion queries offline by running time backwards
- Encode a two-sided constraint by doubling the vertices
|
c++20 |
| Dijkstra |
- Write Dijkstra with a priority queue and lazy deletion
- Explain why a negative edge breaks it, with a four-vertex counterexample
- Reconstruct a shortest path and count how many there are
- Layer the graph to answer "with at most k free moves"
|
c++20 |
| Negative weights |
- Relax every edge n-1 times, and detect a negative cycle with one more round
- Mark the vertices that have no shortest path at all
- Write Floyd-Warshall with the intermediate vertex in the outermost loop
- Choose between all-pairs Floyd-Warshall and n runs of Dijkstra
|
c++20 |
| Spanning trees |
- Write Kruskal with union-find and Prim with a heap
- Say why the greedy choice is safe, using the cut property
- Show that an MST does not contain shortest paths
- Use the MST to answer bottleneck questions
|
c++20 |
| Tree DP |
- Write a subtree DP as one iterative post-order sweep
- Derive a rerooting transition and answer for every vertex in linear time
- Handle a merge that has no inverse, using the runner-up
- Recognise when a problem is asking you to reroot
|
c++20 |