Algorithmic Problem Solving
Time Complexity Ladder — Remember O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). For ZIO constraints: n≤10⁸ allows O(n), n≤10⁶ allows O(n log n), n≤5000 allows O(n²), n≤20 allows O(2ⁿ).
LIFO-FIFO Stack-Queue — Last In First Out = Stack (DFS, recursion simulation, bracket matching). First In First Out = Queue (BFS, level-order traversal). Stack goes deep, Queue goes wide.
DP Table Direction — For DP problems, fill smaller subproblems first. If recurrence is dp[i] = f(dp[i-1], dp[i-2]), iterate i from small to large. For intervals dp[i][j], iterate by increasing length (j-i).
BFS for Unweighted Shortest Path — In unweighted graphs or grids, BFS guarantees shortest path in first visit. Use queue, mark visited immediately on enqueue (not dequeue) to avoid duplicates and ensure O(V+E) time.
Greedy Exchange Argument — To verify greedy correctness: assume optimal solution differs from greedy choice, then show you can "exchange" to make it match greedy without worsening cost, proving greedy is optimal.
DFS Recursion = Stack Simulation — Any DFS recursion can be converted to explicit stack: push initial state, while stack not empty pop state, process it, push children. Useful when recursion depth exceeds limits.
Dijkstra's Non-Negative Rule — Dijkstra works only with non-negative edge weights. For negative weights, use Bellman-Ford (O(VE)). Remember: Dijkstra = priority queue + greedy; once vertex finalized, never revisited.
Tree = N-1 Edges Connected — A tree with N nodes has exactly N-1 edges and is connected. Any connected graph with N nodes and N-1 edges is a tree. No cycles in trees.
Combinatorics and Discrete Mathematics
nCr = nC(n-r) Symmetry — C(n,r) = C(n,n-r), so compute the smaller one. Use C(n,r) = n!/(r!(n-r)!) but calculate iteratively: C(n,r) = C(n-1,r-1) + C(n-1,r) to avoid overflow with large factorials.
Even × Odd Parity Rules — Even ± Even = Even; Odd ± Odd = Even; Even ± Odd = Odd. Even × Anything = Even; Odd × Odd = Odd. Useful for eliminating impossible configurations quickly.
Pigeonhole: n+1 into n — If n+1 pigeons occupy n holes, at least one hole has ≥2 pigeons. Generalized: ⌈(n+1)/k⌉ items in k boxes guarantees one box with ≥⌈(n+1)/k⌉ items.
Modular Arithmetic (a+b)%m — (a+b) mod m = ((a mod m) + (b mod m)) mod m. Similarly for multiplication. For subtraction, add m if result negative: (a-b+m) mod m. Prevents overflow in competitive programming.
Inclusion-Exclusion Two Sets — |A∪B| = |A| + |B| - |A∩B|. For three: |A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |A∩C| + |A∩B∩C|. Alternating signs: add singles, subtract pairs, add triples.
GCD(a,b) via Euclidean — GCD(a,b) = GCD(b, a mod b), repeat until remainder is 0. The last non-zero remainder is GCD. Faster than prime factorization; runs in O(log min(a,b)) steps.
Ad-Hoc Problem Patterns
Off-by-One: Fencepost Error — For N posts, there are N-1 gaps between them. Always check: do you need N or N-1? Test with small cases like N=2 to catch boundary errors early.
Grid 4-Direction Arrays — Use dx[] = {0,0,1,-1} and dy[] = {1,-1,0,0} for right, left, down, up moves. Loop: for(i=0; i<4; i++) explore (x+dx[i], y+dy[i]). Add diagonals with 8 directions if needed.
Binary Search Answer Space — When optimizing "minimum/maximum value that satisfies condition", binary search the answer if monotonic. Code: lo=min_possible, hi=max_possible, while lo<hi test mid, adjust bounds. Answer converges in O(log range) checks.