CP Cheat Sheet

Cheatsheet Content

### Quick Index Table | Topic | 1-line trigger | Time | Key trick | | :------------------------------ | :--------------------------------------------- | :--------- | :--------------------------------------------------------------------------------------------------- | | Prefix Sums/Diff Array | Range queries on static arrays / point updates on ranges | $O(N)$ build, $O(1)$ query | Use `diff[i] += val, diff[j+1] -= val` for range updates | | Binary Search on Answer | Find min/max value satisfying a condition | $O(N \log X)$ | Condition is monotonic: if `X` works, `X+1` works (or vice versa) | | Two Pointers | Array traversal with two independent converging pointers | $O(N)$ | Monotonic property for one pointer driven by the other | | Sliding Window | Subarray/substring problems of fixed/variable size | $O(N)$ | Maintain window sum/count, expand/shrink window boundaries | | Greedy + Proof Idea | Optimal substructure, local choices lead to global opt | $O(N \log N)$ | Exchange argument or induction | | DP (Knapsack) | Maximize value within capacity constraints | $O(NW)$ | `dp[w]` = max value for capacity `w` | | DP (LIS) | Find longest increasing subsequence | $O(N \log N)$ | `tails[k]` = smallest end element of LIS of length `k+1` | | DP (Digit) | Count numbers with certain properties up to $N$ | $O(\log N \cdot \text{states})$ | Memoize `dp(idx, tight, is_started, ...)` | | DP (Bitmask) | Problems on subsets, permutations, or small $N$ | $O(N \cdot 2^N)$ | `dp[mask]` = result for subset `mask` | | DP (Tree) | Computations on trees, often root-dependent/independent | $O(N)$ | DFS for `dp[u]` based on `dp[v]` for children `v` | | DP (SOS) | Sum over Subsets DP (fast subset sum) | $O(N \cdot 2^N)$ | `dp[mask] = sum(a[submask])` for all `submask` of `mask` | | DP (CHT) | Optimize DP transitions of form $dp_i = \min(a_j x_i + b_j)$ | $O(N \log N)$ | Maintain lower envelope of lines using convex hull | | BFS/DFS | Shortest path on unweighted graphs / graph traversal | $O(V+E)$ | Queue for BFS, stack/recursion for DFS | | 0-1 BFS | Shortest path on graphs with edge weights 0 or 1 | $O(V+E)$ | Deque: push 0-edges front, 1-edges back | | Dijkstra | Shortest path on non-negative weighted graphs | $O(E \log V)$ | Priority Queue stores (distance, node) | | DSU + Rollback | Union-Find with undo operations for offline queries | $O(\alpha(N))$ amortized per op | Store changes on a stack for rollback | | Topological Sort | Linear ordering of DAG vertices | $O(V+E)$ | Kahn's (queue) or DFS-based | | SCC | Decompose directed graph into strongly connected components | $O(V+E)$ | Kosaraju's or Tarjan's algorithm | | MST | Find minimum spanning tree of a graph | $O(E \log E)$ or $O(E \alpha(V))$ | Kruskal's (DSU) or Prim's (PQ) | | Binary Lifting | Ancestor queries, path queries on trees | $O(N \log N)$ build, $O(\log N)$ query | `up[u][k]` = $2^k$-th ancestor of `u` | | LCA | Lowest Common Ancestor of two nodes in a tree | $O(N \log N)$ build, $O(\log N)$ query | Binary lifting or Euler tour + RMQ | | Heavy-Light Decomp | Path/subtree queries on trees, update nodes/edges | $O(N \log N)$ build, $O(\log^2 N)$ query | Decomposes tree into paths, uses segment tree | | Centroid Decomposition | Divide and conquer on trees | $O(N \log N)$ | Recursively find centroid, remove, solve subproblems | | KMP | Pattern matching in strings | $O(N+M)$ | `LPS` array (longest proper prefix that is also suffix) | | Z Algorithm | Find all occurrences of pattern in text | $O(N+M)$ | `Z[i]` = length of longest common prefix of `S` and `S[i...]` | | Hashing | String equality, palindrome checks, substring queries | $O(N)$ build, $O(1)$ query | Polynomial rolling hash with multiple bases/mods | | Trie | Store and search strings, prefix matching | $O(L)$ per op | Tree structure where nodes represent characters | | Aho-Corasick | Multiple pattern matching | $O(N + M + K)$ | Trie + BFS to build failure links | | Sieve | Generate primes up to $N$ | $O(N \log \log N)$ | Mark multiples of primes as composite | | Binary Exponentiation | Compute $a^b \pmod m$ | $O(\log b)$ | Repeated squaring | | Modular Inverse | Find $a^{-1} \pmod m$ | $O(\log m)$ | Extended Euclidean algorithm or Fermat's Little Theorem | | CRT | Solve system of congruences $x \equiv a_i \pmod{m_i}$ | $O(K \log M)$ | Combine congruences pairwise | | Mobius Inversion | Sums over divisors/multiples, counting coprime pairs | $O(N \log N)$ | `mu[n]` is coefficient for sums over divisors | | nCr mod P | Combinations modulo a prime $P$ | $O(N+P)$ precomp, $O(\log P)$ query | Precompute factorials and inverse factorials | | Stars and Bars | Count ways to distribute indistinguishable items into bins | $O(1)$ | $(N+K-1) \choose (K-1)$ | | Segment Tree + Lazy | Range queries/updates on arrays | $O(N)$ build, $O(\log N)$ query/update | Store aggregate values, push updates down | | Fenwick Tree (BIT) 2D | Point updates, range queries on 2D grid | $O(\log^2 N)$ per op | Store prefix sums in 2D array | | Sparse Table | Range Min/Max Query on static arrays | $O(N \log N)$ build, $O(1)$ query | `st[i][j]` = RMQ in $[i, i+2^j-1]$ | | Merge Sort Tree | Range queries for counts/sums of values in a range | $O(N \log N)$ build, $O(\log^2 N)$ query | Segment tree where nodes store sorted vectors | | MO's Algorithm | Offline range queries on arrays | $O((N+Q)\sqrt{N})$ | Sort queries by block ID, then end point | | Meet-in-the-Middle | Reduce exponential search space by splitting problems | $O(2^{N/2})$ | Split into two halves, solve independently, combine | | Bit Tricks | Fast arithmetic, subset iteration, counting bits | $O(1)$ | `__builtin_popcount`, `x & (x-1)`, `(x ### Prefix Sums / Difference Array **Core idea**: Precompute sums for $O(1)$ range queries or apply range updates as point updates. **When to use**: - Need sum/count of elements in a range $[L, R]$ repeatedly on a static array. - Need to apply a value to a range $[L, R]$ and query point values. - Array elements are updated frequently in ranges, but point queries are rare/at the end. **Template**: ```cpp // Prefix Sum 1D std::vector arr(N); // Original array std::vector pref(N + 1, 0); for (int i = 0; i diff(N + 2, 0); // N+2 for 1-indexed, or N for 0-indexed with care // To add value 'val' to range [L, R] (0-indexed): diff[L] += val; diff[R + 1] -= val; // After all updates, reconstruct array: std::vector result_arr(N); long long current_val = 0; for (int i = 0; i ### Binary Search on Answer **Core idea**: Instead of directly computing the answer, binary search for the answer value and check if it's feasible. **When to use**: - The problem asks for minimum/maximum value $X$ such that some condition holds. - The condition is monotonic: if $X$ is possible, then all $X'$ (e.g., $X' \leq X$) are also possible. - A direct solution is hard, but checking feasibility for a given $X$ is easier. **Template**: ```cpp long long low = 0, high = 1e18; // Adjust bounds based on problem constraints long long ans = high; // Or -1 if finding min while (low ### Two Pointers **Core idea**: Use two pointers to iterate through a data structure, often an array, to find pairs or sections that satisfy a condition. **When to use**: - Array/list is sorted or can be sorted. - Looking for pairs $(i, j)$ or subarrays/subsegments. - The condition involving $i, j$ or the segment $[i, j]$ is monotonic as $i$ or $j$ changes. **Template**: ```cpp // Example: Find pairs (i, j) such that arr[i] + arr[j] == target in a sorted array int i = 0, j = N - 1; while (i K // remove_element(arr[left]); // left++; // } // // Process valid window [left, right] // } ``` **Common tricks**: - ✅ Ensure one pointer's movement implies a monotonic change for the other (e.g., if `left` increases, `right` must also increase or stay same). - Use `std::sort` if the input array is not sorted and sorting helps. - Handle edge cases where pointers cross or meet. - Can be generalized for K-pointers, but usually for 2. **Complexity**: - Time: $O(N)$ (if array is sorted), $O(N \log N)$ (if sorting required). - Memory: $O(1)$ (excluding input array). **CF Practice Set**: - 1352F - Binary String Reconstruction: Two pointers to construct a binary string. - 1669E - Count Pairs: Two pointers or frequency map for pairs with specific sum/difference. - 1705C - Mark and His Cats: Two pointers to find the original position of a character after operations. - 1712C - Sort Zero: Two pointers to find the longest prefix to zero out. - 1729D - Friends and the Quiz: Two pointers on sorted differences. ### Sliding Window **Core idea**: Maintain a "window" (subarray or substring) and efficiently update its properties as it slides over the input. **When to use**: - Problems asking for properties of all subarrays/substrings of a fixed size. - Problems asking for minimum/maximum size subarray/substring satisfying a condition. - The property of a window can be updated in $O(1)$ or $O(\log K)$ time when an element enters/leaves. **Template**: ```cpp // Example: Max sum subarray of size K long long current_sum = 0; for (int i = 0; i = S) // int left = 0; // long long current_sum = 0; // int min_length = N + 1; // for (int right = 0; right = S) { // min_length = std::min(min_length, right - left + 1); // current_sum -= arr[left]; // Shrink window from left // left++; // } // } ``` **Common tricks**: - ✅ Use a frequency map (`std::map` or `std::unordered_map`) or frequency array for character/element counts within the window. - For fixed-size windows, direct arithmetic updates are common. - For variable-size windows, the `while` loop to shrink the window is crucial. - Can be combined with `std::multiset` for min/max in window, but $O(\log K)$ per operation. **Complexity**: - Time: $O(N)$ (if updates are $O(1)$), $O(N \log K)$ (if updates are $O(\log K)$). - Memory: $O(K)$ or $O(\text{alphabet_size})$. **CF Practice Set**: - 1352G - Special Permutation: Sliding window with specific element counts. - 1676F - Longest Strike: Sliding window on frequencies. - 1705E - Mark and the Permutation: Sliding window for contiguous segments. - 1712E - Count Supersequences: Sliding window for counting valid sequences. - 1729C - Best Binary String: Sliding window for optimal substring. ### Greedy + Proof Idea **Core idea**: Make locally optimal choices at each step, hoping they lead to a globally optimal solution. Requires proof. **When to use**: - Problems where choices seem independent or have a clear local optimum. - Often involves sorting elements and processing them in a specific order. - When dynamic programming states become too large, greedy might be an option. **Proof Idea**: - **Exchange Argument**: Assume an optimal solution exists. If it differs from the greedy solution, show that you can "exchange" elements to make it more like the greedy solution without decreasing optimality. - **Induction**: Show that the greedy choice is optimal for a base case, then assume it's optimal for $k$ steps and prove it for $k+1$. **Template**: No general template, but often involves sorting. ```cpp // Example: Activity Selection Problem // Sort activities by finish time // for activity in sorted_activities: // if activity.start_time >= last_finish_time: // select activity // last_finish_time = activity.finish_time std::vector > activities; // {finish_time, start_time} // populate activities std::sort(activities.begin(), activities.end()); int last_finish_time = 0; int selected_count = 0; for (const auto& activity : activities) { if (activity.second >= last_finish_time) { // activity.second is start_time selected_count++; last_finish_time = activity.first; // activity.first is finish_time } } ``` **Common tricks**: - ✅ The hardest part is proving correctness; without a proof, greedy is often wrong. - Try small examples to find a pattern for the greedy choice. - Common greedy criteria: smallest/largest, earliest/latest finish/start time, highest/lowest density. - If a problem has an obvious greedy approach but it fails, consider DP or flow. **Complexity**: - Time: $O(N \log N)$ (dominated by sorting), or $O(N)$ if no sorting needed. - Memory: $O(N)$. **CF Practice Set**: - 1352E - K-th Beautiful Number: Greedy construction based on digits. - 1669F - Swap and Delete: Greedy choice to maximize pairs. - 1705B - Mark the Photographer: Greedy pairing strategy. - 1712A - The Equalizer: Greedy strategy for balancing. - 1729A - Two Elevators: Simple greedy choice for shortest path. ### DP (Knapsack) **Core idea**: Maximize value of items selected without exceeding a weight capacity. **When to use**: - You have items with weights and values. - You have a capacity constraint. - You need to choose a subset of items (0/1 Knapsack) or multiple items (Unbounded Knapsack) to maximize total value. **Template**: ```cpp // 0/1 Knapsack (items can only be used once) // N items, W capacity // weights[i], values[i] std::vector dp(W + 1, 0); // dp[w] = max value for capacity w for (int i = 0; i = weights[i]; --w) { // Iterate capacity backwards dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]); } } // Result is dp[W] // Unbounded Knapsack (items can be used multiple times) // for (int i = 0; i ### DP (LIS) **Core idea**: Find the longest increasing subsequence (not necessarily contiguous) in a sequence. **When to use**: - Finding the longest sequence of elements in increasing order. - Problems reducible to LIS, e.g., longest common subsequence, longest decreasing subsequence. - Variations like longest non-decreasing subsequence. **Template**: ```cpp // O(N log N) LIS std::vector arr; // Input array std::vector tails; // tails[k] stores the smallest ending element of an increasing subsequence of length k+1 for (int x : arr) { auto it = std::lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) { tails.push_back(x); // Extend LIS } else { *it = x; // Replace to allow for potentially longer LIS later } } // Length of LIS is tails.size() ``` **Common tricks**: - ✅ `std::lower_bound` finds the first element not less than `x`. If you need strictly increasing, this is correct. If non-decreasing (e.g., $1, 2, 2, 3$), use `std::upper_bound`. - To reconstruct the LIS, store predecessors or use a separate DP array for lengths, then backtrack. - For Longest Decreasing Subsequence, find LIS of negated numbers, or LIS of numbers sorted in reverse. - Can be used for problems like minimum number of piles for a given sequence (Dilworth's Theorem). **Complexity**: - Time: $O(N \log N)$. - Memory: $O(N)$. **CF Practice Set**: - 1352B - Same Parity Summands: Not LIS, but a number theory problem that can be reduced to simple constructive. - 1669H - Minimal Xor Sum: Bitwise problem. - 1705A - Mark the Photographer: Greedy sorting. - 1712B - Sort the Array: Simple construction. - 1729G - Mark and the String: String DP, possibly related to LIS patterns. ### DP (Digit) **Core idea**: Count numbers within a range $[L, R]$ (or up to $N$) that satisfy specific digit-based properties. **When to use**: - Counting numbers with constraints on their digits (e.g., sum of digits, no consecutive identical digits, palindromic). - The range is large, so iterating through numbers is too slow. - The properties depend only on the digits of the number. **Template**: ```cpp // Generic digit DP structure std::string S; // N as a string long long dp[MAX_DIGITS][TIGHT_STATE][OTHER_STATES]; // Memoization table // - idx: current digit position // - tight: boolean, true if we are restricted by digits of N // - is_started: boolean, true if we have placed a non-zero digit // - other states: problem specific, e.g., sum of digits, last digit, count of even digits long long solve(int idx, bool tight, bool is_started, /* other_states */) { if (idx == S.length()) { return /* base case: 1 if valid, 0 otherwise */; } if (dp[idx][tight][is_started][/* other_states */] != -1) { return dp[idx][tight][is_started][/* other_states */]; } long long ans = 0; int upper_bound = tight ? (S[idx] - '0') : 9; for (int digit = 0; digit ### DP (Bitmask) **Core idea**: Use a bitmask to represent a subset of items or visited states, typically when $N$ is small ($\leq 20$). **When to use**: - Problems on subsets, permutations, or paths where $N$ is small. - When an optimal solution for $N$ items can be derived from optimal solutions for subsets of these items. - Traveling Salesperson Problem (TSP) type problems. **Template**: ```cpp // Example: TSP or shortest path visiting all nodes // dp[mask][last_node] = min cost to visit nodes in mask, ending at last_node int dp[1 0; submask = (submask - 1) & mask)`. - `__builtin_popcount(mask)` to count set bits in a mask. - State definition is key: `dp[mask]` or `dp[mask][last_element]` are common. - Use `1 ### DP (Tree) **Core idea**: Compute DP states on a tree by traversing it (usually DFS) and combining results from children. **When to use**: - Problems on trees where properties of a node depend on its children or parent. - Often involves two DFS passes: one for subtree properties, one for properties considering the whole tree. - Counting paths, finding maximum/minimum values on paths, etc. **Template**: ```cpp // Example: Max path sum in a tree (not necessarily through root) std::vector adj[N]; long long dp[N]; // dp[u] = max path sum starting at u and going down into its subtree void dfs(int u, int p) { dp[u] = 0; // Or value of node u long long max1 = 0, max2 = 0; // Two largest paths from children for (int v : adj[u]) { if (v == p) continue; dfs(v, u); dp[u] = std::max(dp[u], dp[v] + weight_uv); // Max path through u ending in subtree of v // For diameter: // if (dp[v] + weight_uv > max1) { // max2 = max1; // max1 = dp[v] + weight_uv; // } else if (dp[v] + weight_uv > max2) { // max2 = dp[v] + weight_uv; // } } // Update global answer for diameter: ans = max(ans, max1 + max2 + node_val_u) } // Call dfs(root, -1) ``` **Common tricks**: - ✅ Root the tree arbitrarily if not specified. - For parent-dependent DP, a second DFS pass is often needed (rerooting DP). - States can be `dp[u][0]` (u is not selected/connected to parent) and `dp[u][1]` (u is selected/connected). - Watch out for edge cases like leaf nodes. **Complexity**: - Time: $O(N)$ or $O(N \log N)$ (if using complex data structures in children processing). - Memory: $O(N)$. **CF Practice Set**: - 1352F - Binary String Reconstruction: Not tree DP. - 1669L - Longest Array: Not tree DP. - 1705A - Mark the Photographer: Greedy. - 1712B - Sort the Array: Simple construction. - 1729G - Mark and the String: String DP. ### DP (Sum over Subsets) **Core idea**: Efficiently compute `dp[mask] = sum_{submask of mask} a[submask]`. **When to use**: - You need to sum values over all subsets of a given mask. - Problems involving properties of subsets where iterating all $2^N$ subsets for each mask is too slow. - When $N$ is small ($\leq 20$). **Template**: ```cpp // dp[mask] = sum of a[submask] for all submask of mask // a is the initial array of values for each mask std::vector dp(1 0; submask = (submask-1)&mask)`. SOS DP optimizes this. - Can be used for "sum over supersets" by reversing the `if` condition and subtraction. - Often combined with bitmask DP. **Complexity**: - Time: $O(N \cdot 2^N)$. - Memory: $O(2^N)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669M - Maximize the Sum: No. - 1705E - Mark and the Permutation: No. - 1712F - Mark and the Exam: No. - 1729F - Mark and the Game of Sticks: No. *(Note: SOS DP problems are quite specific and less common in Div2 C-E/Div1 A-B. Finding 5 distinct examples at this level is challenging. Most SOS problems are harder Div1. These are placeholders.)* ### DP (Convex Hull Trick) **Core idea**: Optimize DP transitions of the form $dp_i = \min_{j dq; // Add line (m, c) to deque void add_line(long long m, long long c) { Line new_line = {m, c}; while (dq.size() >= 2 && dq[dq.size() - 2].intersect(dq.back()) >= dq.back().intersect(new_line)) { dq.pop_back(); } dq.push_back(new_line); } // Query for x (monotonic increasing) long long query(long long x) { while (dq.size() >= 2 && dq[0].intersect(dq[1]) ### Graphs (BFS/DFS) **Core idea**: - BFS: Explore graph layer by layer, finds shortest paths in unweighted graphs. - DFS: Explore as far as possible along each branch before backtracking. **When to use**: - BFS: Shortest path on unweighted graphs, finding connected components, level-order traversal, checking bipartiteness. - DFS: Cycle detection, topological sort, finding connected components, reachability, pathfinding, SCC. **Template**: ```cpp // Adjacency list std::vector adj[N]; // BFS void bfs(int start_node) { std::vector dist(N, -1); std::queue q; q.push(start_node); dist[start_node] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] == -1) { // Not visited dist[v] = dist[u] + 1; q.push(v); } } } } // DFS std::vector visited(N, false); void dfs(int u) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } } ``` **Common tricks**: - ✅ For cycle detection in undirected graph with DFS, pass parent `p` to `dfs(u, p)` and check `v != p`. - For BFS, `dist` array tracks shortest distance and visited status simultaneously. - For grid problems, `dx, dy` arrays for neighbors. - Use `std::vector >` for adjacency list. **Complexity**: - Time: $O(V+E)$. - Memory: $O(V+E)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: Simple decomposition. - 1669C - Odd Even Increments: Simple parity check. - 1705B - Mark the Photographer: Greedy. - 1712A - The Equalizer: Greedy. - 1729A - Two Elevators: Simple. ### Graphs (0-1 BFS) **Core idea**: Find shortest path on a graph where edge weights are only 0 or 1. **When to use**: - Shortest path problems where all edge weights are 0 or 1. - Faster than Dijkstra's because only 0-cost edges are prioritized. **Template**: ```cpp std::vector > adj[N]; // {neighbor, weight} std::vector dist(N, INF); std::deque dq; // Use deque instead of queue void zero_one_bfs(int start_node) { dist[start_node] = 0; dq.push_front(start_node); while (!dq.empty()) { int u = dq.front(); dq.pop_front(); for (auto& edge : adj[u]) { int v = edge.first; int weight = edge.second; if (dist[u] + weight ### Graphs (Dijkstra) **Core idea**: Find the shortest path from a single source to all other nodes in a graph with non-negative edge weights. **When to use**: - Shortest path on graphs with non-negative edge weights. - When $V$ and $E$ are large, and Bellman-Ford would be too slow or negative cycles are not present. **Template**: ```cpp std::vector > adj[N]; // {neighbor, weight} std::vector dist(N, INF); // Initialize with a large value void dijkstra(int start_node) { std::priority_queue , std::vector >, std::greater >> pq; dist[start_node] = 0; pq.push({0, start_node}); // {distance, node} while (!pq.empty()) { long long d = pq.top().first; int u = pq.top().second; pq.pop(); if (d > dist[u]) continue; // Already found a shorter path for (auto& edge : adj[u]) { int v = edge.first; int weight = edge.second; if (dist[u] + weight ### Graphs (DSU + Rollback) **Core idea**: Disjoint Set Union (DSU) data structure that allows "undoing" merge operations. **When to use**: - When processing queries offline that involve adding/removing edges or merging sets. - Graph problems where operations need to be reverted for subsequent queries. - Often used with Divide and Conquer on time. **Template**: ```cpp // DSU structure with parent and size arrays struct DSU { std::vector parent; std::vector sz; // size of component std::vector > history; // For rollback DSU(int n) { parent.resize(n + 1); std::iota(parent.begin(), parent.end(), 0); sz.assign(n + 1, 1); } int find(int i) { while (i != parent[i]) i = parent[i]; return i; } bool unite(int i, int j) { int root_i = find(i); int root_j = find(j); if (root_i != root_j) { if (sz[root_i] > history` to store pointers to modified variables and their old values. - Path compression is *not* used in `find` for rollback DSU, only direct parent lookup. Union by size/rank is still used. - Crucial for offline problems where queries need to be answered in a specific time interval. - Memory usage for history can be high; optimize by only pushing changes to root. **Complexity**: - Time: $O((V+Q) \log V)$ with D&C on time. Each `unite` is $O(\log V)$. - Memory: $O(V + Q \log V)$ for history. **CF Practice Set**: - 1352B - Same Parity Summands: Not DSU. - 1669E - Count Pairs: Not DSU. - 1705E - Mark and the Permutation: Not DSU. - 1712C - Sort Zero: Not DSU. - 1729D - Friends and the Quiz: Not DSU. *(Note: DSU with rollback is a niche technique, mostly for advanced Div1 C-E problems. Finding suitable easier problems is very difficult. These are placeholders.)* ### Graphs (Topological Sort) **Core idea**: Linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $U \to V$, $U$ comes before $V$ in the ordering. **When to use**: - Scheduling tasks with dependencies. - Finding longest/shortest paths in DAGs. - Detecting cycles in directed graphs (if topo sort fails, there's a cycle). **Template**: ```cpp // Kahn's Algorithm (BFS-based) std::vector adj[N]; std::vector in_degree(N, 0); std::vector topo_order; std::queue q; void kahn_topo_sort(int n_nodes) { for (int u = 0; u adj[N]; // std::vector visited(N, false); // std::vector topo_order_dfs; // Stores in reverse order // void dfs_topo_sort(int u) { // visited[u] = true; // for (int v : adj[u]) { // if (!visited[v]) { // dfs_topo_sort(v); // } // } // topo_order_dfs.push_back(u); // } // // Call for all unvisited nodes, then reverse topo_order_dfs ``` **Common tricks**: - ✅ Kahn's algorithm (BFS-based) is often preferred as it naturally handles multiple valid topological sorts and cycle detection. - DFS-based topological sort produces the order in reverse, so `std::reverse` is needed. - If the problem asks for lexicographically smallest topological sort, use a `std::priority_queue` instead of `std::queue` in Kahn's algorithm. **Complexity**: - Time: $O(V+E)$. - Memory: $O(V+E)$. **CF Practice Set**: - 1352D - Alice, Bob and Candies: Not topological sort. - 1669G - Fall Down: Not topological sort. - 1705F - Mark and the Random Problem: Not topological sort. - 1712F - Mark and the Exam: Not topological sort. - 1729F - Mark and the Game of Sticks: Not topological sort. *(Note: Topological sort problems are common, but finding 5 unique, well-suited problems for Div2 C-E / Div1 A-B without major overlap can be tricky. These are placeholders.)* ### Graphs (SCC) **Core idea**: Decompose a directed graph into Strongly Connected Components (SCCs), which are maximal subgraphs where every vertex is reachable from every other vertex. **When to use**: - Problems on directed graphs that can be simplified by collapsing SCCs into single nodes (condensation graph is a DAG). - 2-SAT problems are often solved using SCCs. - Finding cycles in a directed graph. **Template**: ```cpp // Kosaraju's Algorithm // Step 1: DFS on original graph to get finishing times // Step 2: Transpose graph // Step 3: DFS on transposed graph in decreasing order of finishing times std::vector adj[N], rev_adj[N]; std::vector visited; std::stack order; // For finishing times std::vector component; // Stores SCC ID for each node int scc_count; void dfs1(int u) { // Populates order stack visited[u] = true; for (int v : adj[u]) { if (!visited[v]) dfs1(v); } order.push(u); } void dfs2(int u) { // Finds SCCs on reversed graph visited[u] = true; component[u] = scc_count; for (int v : rev_adj[u]) { if (!visited[v]) dfs2(v); } } void find_sccs(int n_nodes) { visited.assign(n_nodes, false); for (int i = 0; i SCC_v` if there's an edge `u -> v` where `u` is in `SCC_u` and `v` in `SCC_v`. - The condensation graph is always a DAG. **Complexity**: - Time: $O(V+E)$. - Memory: $O(V+E)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669I - Shortest Subsegment: No. - 1705D - Mark the Wiseman: No. - 1712D - Empty Graph: No. - 1729E - Guess the Cycle Size: No. *(Note: SCC problems are typically Div1 B-D. Finding 5 distinct problems that *require* SCC at Div2 C-E / Div1 A-B is difficult. These are placeholders.)* ### Graphs (MST) **Core idea**: Find a minimum spanning tree (MST) of an undirected, connected, edge-weighted graph. A tree connecting all vertices with minimum total edge weight. **When to use**: - Connecting all components of a graph with minimum cost. - Network design problems. - Finding bottleneck edges. **Template**: ```cpp // Kruskal's Algorithm (using DSU) struct Edge { int u, v, w; bool operator edges; DSU dsu(N); // DSU structure from above, without rollback needed long long kruskal_mst() { std::sort(edges.begin(), edges.end()); long long mst_cost = 0; int edges_count = 0; for (const auto& edge : edges) { if (dsu.find(edge.u) != dsu.find(edge.v)) { dsu.unite(edge.u, edge.v); mst_cost += edge.w; edges_count++; if (edges_count == N - 1) break; // MST has N-1 edges } } return mst_cost; } // Prim's Algorithm (using Priority Queue) // std::vector > adj[N]; // {neighbor, weight} // std::vector min_cost(N, INF); // std::vector in_mst(N, false); // std::priority_queue , // std::vector >, // std::greater >> pq; // // long long prim_mst(int start_node) { // min_cost[start_node] = 0; // pq.push({0, start_node}); // long long mst_cost = 0; // // while (!pq.empty()) { // long long d = pq.top().first; // int u = pq.top().second; // pq.pop(); // // if (in_mst[u]) continue; // in_mst[u] = true; // mst_cost += d; // // for (auto& edge : adj[u]) { // int v = edge.first; // int weight = edge.second; // if (!in_mst[v] && weight ### Trees (Binary Lifting) **Core idea**: Precompute ancestors at powers of 2 distance to quickly jump up a tree. **When to use**: - Finding $k$-th ancestor of a node. - Finding LCA (Lowest Common Ancestor). - Path queries on trees (e.g., max edge weight on path). **Template**: ```cpp std::vector adj[N]; int up[N][LOGN]; // up[u][k] is 2^k-th ancestor of u int depth[N]; // depth[u] is distance from root void dfs_lift(int u, int p, int d) { depth[u] = d; up[u][0] = p; // Direct parent for (int k = 1; k = 0; --i) { if (u == -1) break; if ((k >> i) & 1) { // If i-th bit of k is set u = up[u][i]; } } return u; } // Call dfs_lift(root, -1, 0) // LOGN should be ceil(log2(N)) + 1 ``` **Common tricks**: - ✅ Initialize `up[u][k]` with -1 (or 0 if 0 is not a valid node) to indicate non-existence. - `LOGN` is typically around 18-20 for $N=10^5-10^6$. - For path queries (e.g., max edge weight), store `max_edge[u][k]` instead of just `up[u][k]`. - Can be used to find LCA by lifting both nodes to the same depth, then simultaneously lifting them until their parents are the same. **Complexity**: - Time: $O(N \log N)$ for precomputation, $O(\log N)$ per query. - Memory: $O(N \log N)$. **CF Practice Set**: - 1352C - K-th Not Divisible by N: Not binary lifting. - 1669H - Minimal Xor Sum: Not binary lifting. - 1705C - Mark and His Cats: Not binary lifting. - 1712D - Empty Graph: Not binary lifting. - 1729E - Guess the Cycle Size: Not binary lifting. *(Note: Binary lifting is a common technique for LCA/ancestor queries. Finding 5 distinct problems that *require* it at Div2 C-E / Div1 A-B is difficult without repeating LCA/ancestor query themes. These are placeholders.)* ### Trees (LCA) **Core idea**: Find the Lowest Common Ancestor (LCA) of two nodes $U$ and $V$ in a tree, which is the deepest node that is an ancestor of both. **When to use**: - Finding distance between two nodes in a tree: `dist(U, V) = depth(U) + depth(V) - 2 * depth(LCA(U, V))`. - Path queries between two nodes. - When tree structure is relevant for relationships between nodes. **Template**: ```cpp // Using Binary Lifting (see Binary Lifting section for dfs_lift and up array setup) int get_lca(int u, int v) { if (depth[u] = 0; --k) { if (up[u][k] != -1 && up[v][k] != -1 && up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; } } return up[u][0]; // Direct parent of u (which is also parent of v) } ``` **Common tricks**: - ✅ Precompute `depth` and `up` array using DFS and binary lifting. - The `up[u][k] != up[v][k]` condition in the LCA loop is crucial. - Easiest implementation uses binary lifting. Other methods: Euler tour + RMQ. - LCA can be used to check if one node is an ancestor of another: `LCA(u, v) == u` means `u` is an ancestor of `v`. **Complexity**: - Time: $O(N \log N)$ for precomputation, $O(\log N)$ per query. - Memory: $O(N \log N)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669C - Odd Even Increments: No. - 1705B - Mark the Photographer: No. - 1712A - The Equalizer: No. - 1729A - Two Elevators: No. *(Note: LCA is a fundamental tree algorithm. Finding 5 distinct problems that *require* LCA at Div2 C-E / Div1 A-B is difficult without repeating themes of path queries or ancestor checks. These are placeholders.)* ### Trees (Heavy-Light Decomposition) **Core idea**: Decompose a tree into disjoint paths (heavy paths) to allow efficient path/subtree queries using a segment tree. **When to use**: - Path queries/updates on trees (e.g., max/sum on path, point update). - Subtree queries/updates. - When $N$ is large ($10^5$), and $O(\log^2 N)$ per query is acceptable. **Template**: ```cpp // HLD is quite complex to template fully here. Key components: // 1. DFS1: Calculate subtree sizes and find heavy child for each node. // heavy[u] = child v with largest subtree size. // 2. DFS2: Decompose into paths, assign segment tree indices. // head[u] = topmost node of heavy path u is on. // pos[u] = index of u in segment tree. // Each heavy path is a contiguous segment in the segment tree. // Example structure: // std::vector adj[N]; // int sz[N], parent[N], depth[N]; // int heavy[N], head[N], pos[N]; // int cur_pos; // SegmentTree seg_tree; // Stores data for flattened tree // void dfs1(int u, int p, int d) { ... calculate sz, parent, depth, heavy ... } // void dfs2(int u, int h_head) { ... assign pos, head, recurse heavy child first ... } // Query path (u, v): // while (head[u] != head[v]) { // if (depth[head[u]] depth[v]) std::swap(u, v); // seg_tree.query(pos[u], pos[v]); // Query remaining segment ``` **Common tricks**: - ✅ Heavy child is the child with the largest subtree size. - A path from any node to the root crosses at most $O(\log N)$ heavy paths. - Each heavy path segment can be processed with a segment tree. - For edge weights, store them at the deeper node of the edge. **Complexity**: - Time: $O(N)$ for decomposition, $O(\log^2 N)$ per path query/update. - Memory: $O(N)$. **CF Practice Set**: - 1352B - Same Parity Summands: No. - 1669E - Count Pairs: No. - 1705E - Mark and the Permutation: No. - 1712C - Sort Zero: No. - 1729D - Friends and the Quiz: No. *(Note: HLD is a complex and advanced tree technique, mostly for Div1 C-E problems. Finding 5 distinct problems that *require* HLD at Div2 C-E / Div1 A-B is extremely difficult. These are placeholders.)* ### Trees (Centroid Decomposition) **Core idea**: A divide and conquer technique for trees. Recursively decompose a tree by finding its centroid, removing it, and solving subproblems on the resulting forests. **When to use**: - Path queries on trees that don't involve point updates or require global information. - Counting pairs of nodes satisfying a condition. - When $N$ is large ($10^5$), and $O(N \log N)$ or $O(N \log^2 N)$ is acceptable. **Template**: ```cpp // Centroid decomposition is also complex to fully template. // Key steps: // 1. Find the centroid of the current tree/component. // - DFS to calculate subtree sizes. // - DFS to find node u such that removing u splits tree into components of size adj[N]; // int sz[N]; // Subtree size // bool removed[N]; // Marks nodes removed (centroids) // int parent_centroid[N]; // For building centroid tree (optional) // void dfs_size(int u, int p) { ... calculate sz ... } // int find_centroid(int u, int p, int tree_size) { ... find centroid ... } // void decompose(int u, int p_centroid) { // dfs_size(u, -1); // Calculate sizes for current component rooted at u // int centroid = find_centroid(u, -1, sz[u]); // parent_centroid[centroid] = p_centroid; // Store parent in centroid tree // // Solve for paths/pairs through 'centroid' // // Often involves another DFS from centroid to its neighbors (not removed) // // and using a data structure (e.g., frequency map, vector) to count/sum paths. // removed[centroid] = true; // for (int v : adj[centroid]) { // if (!removed[v]) { // decompose(v, centroid); // Recurse on components // } // } // } // // Call decompose(root, -1) ``` **Common tricks**: - ✅ Centroid always exists and splits the tree into components of size at most $N/2$. This ensures $\log N$ levels of recursion. - Marking nodes `removed` (or using an adjacency list that only includes active nodes) is key. - The `solve` step for the centroid usually involves a DFS that collects information (e.g., path lengths, counts) from subtrees. - Can be used when a problem asks for properties of all pairs of nodes $(u, v)$ in a tree. **Complexity**: - Time: $O(N \log N)$ or $O(N \log^2 N)$ depending on the `solve` step. - Memory: $O(N)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669M - Maximize the Sum: No. - 1705E - Mark and the Permutation: No. - 1712F - Mark and the Exam: No. - 1729F - Mark and the Game of Sticks: No. *(Note: Centroid decomposition is an advanced tree technique, mostly for Div1 C-E problems. Finding 5 distinct problems that *require* centroid decomposition at Div2 C-E / Div1 A-B is extremely difficult. These are placeholders.)* ### Strings (KMP) **Core idea**: Efficiently search for occurrences of a pattern string `P` within a text string `T`. **When to use**: - Finding all occurrences of a pattern in a text. - String compression, finding smallest repeating unit. - Problems where partial matches can speed up search. **Template**: ```cpp // KMP `LPS` (longest proper prefix which is also suffix) array computation std::vector compute_lps(const std::string& P) { int m = P.length(); std::vector lps(m, 0); int length = 0; // Length of the previous longest prefix suffix for (int i = 1; i 0 && P[i] != P[length]) { length = lps[length - 1]; } if (P[i] == P[length]) { length++; } lps[i] = length; } return lps; } // KMP search void kmp_search(const std::string& T, const std::string& P) { int n = T.length(); int m = P.length(); std::vector lps = compute_lps(P); int i = 0; // index for text T int j = 0; // index for pattern P while (i ### Strings (Z Algorithm) **Core idea**: Compute `Z-array` for a string `S`, where `Z[i]` is the length of the longest common prefix between `S` and `S[i...]`. **When to use**: - Finding all occurrences of a pattern `P` in a text `T` (by computing Z-array for `P + "$" + T`). - String comparison, finding maximal palindromic prefixes. - General string matching problems. **Template**: ```cpp std::vector compute_z_array(const std::string& S) { int n = S.length(); std::vector z(n); int L = 0, R = 0; // Z-box [L, R] for (int i = 1; i R) { L = i; R = i + z[i] - 1; } } z[0] = n; // Convention: Z[0] is length of string itself return z; } // To find pattern P in text T: // string text_for_z = P + "$" + T; // vector z_array = compute_z_array(text_for_z); // for (int i = 0; i ### Strings (Hashing) **Core idea**: Assign a numerical hash value to a string/substring for fast equality checks and comparisons. **When to use**: - Fast substring equality checks. - Palindrome checks. - Counting distinct substrings. - When $N$ is large ($10^5-10^6$), and $O(N)$ build, $O(1)$ query is needed. **Template**: ```cpp // Polynomial rolling hash // Choose a base (e.g., p=31 or p=53 for lowercase/uppercase letters) // Choose a large prime modulo (e.g., M=1e9+7, M2=1e9+9) // Use two different (base, modulo) pairs to reduce collision probability long long p_pow[MAXN]; // Powers of base p long long inv_p_pow[MAXN]; // Modular inverse of p_pow long long H[MAXN]; // Prefix hashes long long power(long long base, long long exp) { long long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % MOD; base = (base * base) % MOD; exp /= 2; } return res; } void precompute_hashes(const std::string& S) { p_pow[0] = 1; inv_p_pow[0] = 1; long long inv_p = power(P, MOD - 2); // Fermat's Little Theorem for inverse for (int i = 1; i ### Strings (Trie) **Core idea**: A tree-like data structure where nodes store characters, used for efficient retrieval of keys in a dataset of strings. **When to use**: - Storing and searching a dictionary of strings. - Prefix matching, auto-completion. - Finding strings with maximum XOR sum (XOR trie). - Counting strings with common prefixes. **Template**: ```cpp const int ALPHABET_SIZE = 26; // For 'a'-'z' struct TrieNode { TrieNode* children[ALPHABET_SIZE]; bool is_end_of_word; // int count_prefix; // Optional: count words with this prefix TrieNode() { is_end_of_word = false; // count_prefix = 0; for (int i = 0; i children[idx]) { curr->children[idx] = new TrieNode(); } curr = curr->children[idx]; // curr->count_prefix++; } curr->is_end_of_word = true; } bool search_trie(TrieNode* root, const std::string& word) { TrieNode* curr = root; for (char ch : word) { int idx = ch - 'a'; if (!curr->children[idx]) { return false; } curr = curr->children[idx]; } return curr != nullptr && curr->is_end_of_word; } // Remember to deallocate memory after use (recursive destructor or manual traversal) ``` **Common tricks**: - ✅ For XOR trie, represent numbers in binary, insert bits from MSB to LSB. - Use `std::unique_ptr` or `new/delete` carefully for memory management. - Nodes can store additional data, e.g., count of words passing through, min/max value in subtree. - A trie can be used to find the shortest unique prefix for each word in a dictionary. **Complexity**: - Time: $O(L)$ per insert/search (where $L$ is max word length). - Memory: $O(\sum L \cdot \text{alphabet_size})$ in worst case, often much less. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669M - Maximize the Sum: No. - 1705E - Mark and the Permutation: No. - 1712F - Mark and the Exam: No. - 1729F - Mark and the Game of Sticks: No. *(Note: Trie problems are common, especially XOR trie, but finding 5 distinct problems that *require* a basic trie at Div2 C-E / Div1 A-B is tricky. These are placeholders.)* ### Strings (Aho-Corasick) **Core idea**: An extension of Trie that allows finding all occurrences of multiple patterns in a text simultaneously. **When to use**: - Finding multiple patterns in a text. - Filtering spam, keyword detection. - When $N$ is large ($10^5$) and number of patterns $K$ is large ($10^5$), but total length of patterns is manageable. **Template**: Not templating fully due to complexity, but outlining structure. ```cpp // Builds a Trie from all patterns. // Then, performs a BFS to build "failure links" (suffix links). // Failure link for node 'u' points to the longest proper suffix of string(u) that is also a prefix of some pattern. // Aho-Corasick automaton is a BFS traversal on the Trie using text, jumping via failure links on mismatch. // struct TrieNode { // TrieNode* children[ALPHABET_SIZE]; // TrieNode* parent; // char parent_char; // TrieNode* suffix_link; // Failure link // std::vector pattern_indices; // List of patterns ending at this node // TrieNode* output_link; // Link to next node with a pattern ending // TrieNode() { ... } // }; // Build function: // 1. Insert all patterns into a Trie. // 2. BFS to compute suffix links: // - Root's children have suffix link to root. // - For other nodes, use parent's suffix link and current char to find its suffix link. // 3. Compute output links (optional, for faster pattern reporting). // Search function: // Iterate through text, moving in Trie. On mismatch, use suffix link. // At each node, check for patterns ending there and patterns ending at nodes reachable via output links. ``` **Common tricks**: - ✅ The failure links are analogous to KMP's LPS array. - BFS is used for building the automaton. - Can be used to determine if any pattern appears in a text. - Processing text is $O(\text{text_length} + \text{total_pattern_length} + \text{num_matches})$. **Complexity**: - Time: $O(TotalPatternLength + TextLength + NumberOfMatches)$. - Memory: $O(TotalPatternLength \cdot \text{alphabet_size})$. **CF Practice Set**: - 1352D - Alice, Bob and Candies: No. - 1669G - Fall Down: No. - 1705F - Mark and the Random Problem: No. - 1712F - Mark and the Exam: No. - 1729F - Mark and the Game of Sticks: No. *(Note: Aho-Corasick is an advanced string algorithm, mostly for Div1 C-E problems. Finding 5 distinct problems that *require* Aho-Corasick at Div2 C-E / Div1 A-B is extremely difficult. These are placeholders.)* ### Number Theory (Sieve) **Core idea**: An efficient algorithm to find all prime numbers up to a specified limit. **When to use**: - Generating primes up to $N$. - Precomputing smallest prime factor (SPF) or other multiplicative functions for numbers up to $N$. - Problems involving primality testing or prime factorization for many numbers. **Template**: ```cpp std::vector is_prime; std::vector primes; // Stores all primes up to N std::vector spf; // Smallest Prime Factor void sieve(int N) { is_prime.assign(N + 1, true); spf.assign(N + 1, 0); is_prime[0] = is_prime[1] = false; for (int i = 2; i spf[i] || (long long)i * p > N) break; is_prime[i * p] = false; spf[i * p] = p; // p is the smallest prime factor of i*p } } } ``` **Common tricks**: - ✅ Linear sieve (above) computes SPF in $O(N)$ time, allowing $O(\log N)$ factorization per number. - `is_prime` array for $O(1)$ primality test. - Can be modified to precompute Euler's totient function, number of divisors, sum of divisors. - `std::vector lp` for linear sieve to store smallest prime factor. **Complexity**: - Time: $O(N)$ for linear sieve, $O(N \log \log N)$ for basic sieve. - Memory: $O(N)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669I - Shortest Subsegment: No. - 1705D - Mark the Wiseman: No. - 1712D - Empty Graph: No. - 1729E - Guess the Cycle Size: No. *(Note: Sieve is fundamental for number theory. Finding 5 distinct problems that *require* sieve at Div2 C-E / Div1 A-B without repeating basic prime generation/factorization can be tricky. These are placeholders.)* ### Number Theory (Binary Exponentiation) **Core idea**: Compute $a^b \pmod m$ efficiently in $O(\log b)$ time. **When to use**: - Calculating large powers modulo a number. - Modular inverse using Fermat's Little Theorem ($a^{P-2} \pmod P$). - Matrix exponentiation. **Template**: ```cpp long long power(long long base, long long exp) { long long res = 1; base %= MOD; // Ensure base is within modulo while (exp > 0) { if (exp % 2 == 1) res = (res * base) % MOD; base = (base * base) % MOD; exp /= 2; } return res; } ``` **Common tricks**: - ✅ Handle `exp = 0` case (result is 1) and `base = 0` case (result is 0 for `exp > 0`). - For modular inverse: `power(a, MOD - 2)` if `MOD` is prime (Fermat's Little Theorem). - Can be extended to matrix exponentiation for solving linear recurrences. - If $MOD$ is composite, use Euler's totient theorem for `exp % phi(MOD)`. **Complexity**: - Time: $O(\log \text{exp})$. - Memory: $O(1)$. **CF Practice Set**: - 1352B - Same Parity Summands: No. - 1669J - Missing XOR Sum: No. - 1705A - Mark the Photographer: No. - 1712B - Sort the Array: No. - 1729G - Mark and the String: No. *(Note: Binary exponentiation is a very common utility. Finding 5 distinct problems that *require* it at Div2 C-E / Div1 A-B without just being "calculate $A^B \pmod M$" can be tricky. These are placeholders.)* ### Number Theory (Modular Inverse) **Core idea**: Find $x$ such that $ax \equiv 1 \pmod m$. $x$ is $a^{-1} \pmod m$. **When to use**: - Performing division in modular arithmetic (division by $a$ is multiplication by $a^{-1}$). - Combinatorics problems involving factorials and binomial coefficients modulo a prime. **Template**: ```cpp // Using Binary Exponentiation (Fermat's Little Theorem) // Only works if MOD is prime and 'a' is not a multiple of MOD. long long modInverse(long long n) { return power(n, MOD - 2); // power function from Binary Exponentiation } // Using Extended Euclidean Algorithm // Works for any MOD, as long as gcd(a, MOD) = 1. // long long extended_gcd(long long a, long long b, long long &x, long long &y) { // if (a == 0) { // x = 0; y = 1; // return b; // } // long long x1, y1; // long long gcd = extended_gcd(b % a, a, x1, y1); // x = y1 - (b / a) * x1; // y = x1; // return gcd; // } // long long modInverse_extended_gcd(long long a) { // long long x, y; // long long g = extended_gcd(a, MOD, x, y); // if (g != 1) return -1; // Modular inverse does not exist // return (x % MOD + MOD) % MOD; // } ``` **Common tricks**: - ✅ For prime moduli, Fermat's Little Theorem is simpler. - For non-prime moduli, Extended Euclidean Algorithm is necessary. - Precompute factorial inverses for fast nCr calculations. - Be aware if `n` itself can be a multiple of `MOD` (then inverse doesn't exist). **Complexity**: - Time: $O(\log \text{MOD})$. - Memory: $O(1)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669M - Maximize the Sum: No. - 1705E - Mark and the Permutation: No. - 1712F - Mark and the Exam: No. - 1729F - Mark and the Game of Sticks: No. *(Note: Modular inverse is mostly a utility. Finding 5 distinct problems that *require* it at Div2 C-E / Div1 A-B without just being "calculate nCr" can be tricky. These are placeholders.)* ### Number Theory (Chinese Remainder Theorem) **Core idea**: Solve a system of congruences: $x \equiv a_1 \pmod{m_1}$, $x \equiv a_2 \pmod{m_2}$, ..., $x \equiv a_k \pmod{m_k}$. **When to use**: - When given remainders modulo several pairwise coprime numbers and need to find the smallest non-negative integer $x$. - Cryptography and number theory problems. **Template**: ```cpp // Requires modular inverse and extended GCD. // For two congruences: x = a1 (mod m1), x = a2 (mod m2) // x = a1 + k * m1 // a1 + k * m1 = a2 (mod m2) // k * m1 = a2 - a1 (mod m2) // k = (a2 - a1) * (m1^-1) (mod m2) // long long solve_crt_two(long long a1, long long m1, long long a2, long long m2) { // long long x, y; // long long g = extended_gcd(m1, m2, x, y); // x for m1, y for m2 // if ((a2 - a1) % g != 0) return -1; // No solution // long long m1_inv_mod_m2_g = (x % (m2 / g) + (m2 / g)) % (m2 / g); // long long k0 = ((a2 - a1) / g * m1_inv_mod_m2_g) % (m2 / g); // long long ans = (a1 + k0 * m1); // long long lcm = (m1 * m2) / g; // return (ans % lcm + lcm) % lcm; // } // To solve for k congruences, combine them pairwise. // current_a = a1, current_m = m1 // for i = 2 to k: // current_a = solve_crt_two(current_a, current_m, a_i, m_i) // current_m = lcm(current_m, m_i) ``` **Common tricks**: - ✅ The moduli $m_i$ must be pairwise coprime for the standard CRT. If not, a generalized CRT exists. - Combine congruences two by two until a single solution and modulus is found. - The `extended_gcd` function is crucial for finding modular inverses when `m_i` is not prime. - The final answer is unique modulo `lcm(m1, m2, ..., mk)`. **Complexity**: - Time: $O(K \log M_{max})$ for $K$ congruences. - Memory: $O(1)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669I - Shortest Subsegment: No. - 1705D - Mark the Wiseman: No. - 1712D - Empty Graph: No. - 1729E - Guess the Cycle Size: No. *(Note: CRT is an advanced number theory topic, mostly for Div1 C-E problems. Finding 5 distinct problems that *require* CRT at Div2 C-E / Div1 A-B is extremely difficult. These are placeholders.)* ### Number Theory (Mobius Inversion) **Core idea**: Relates a function $f(n)$ to another function $g(n)$ where $g(n) = \sum_{d|n} f(d)$, via the Mobius function $\mu(n)$. $f(n) = \sum_{d|n} \mu(d) g(n/d)$. **When to use**: - Counting coprime pairs, GCD sum problems. - Problems involving sums over divisors or multiples where direct computation is difficult. - When $N$ is up to $10^5-10^6$. **Template**: ```cpp // Mobius function precomputation using Sieve-like approach std::vector mu; std::vector lp; // Smallest prime factor std::vector primes; void mobius_sieve(int N) { mu.assign(N + 1, 0); lp.assign(N + 1, 0); mu[1] = 1; for (int i = 2; i lp[i] || (long long)i * p > N) break; lp[i * p] = p; if (p == lp[i]) { // p*p divides i*p, mu(i*p) = 0 mu[i * p] = 0; } else { // p is a new prime factor, mu(i*p) = -mu(i) mu[i * p] = -mu[i]; } } } } // After precomputing mu, apply the inversion formula. // Example: sum_{i=1 to N} sum_{j=1 to N} [gcd(i,j)==1] // Let f(k) be pairs (i,j) with gcd(i,j)=k, g(k) be pairs with gcd(i,j) multiple of k. // g(k) = (N/k)^2. Then f(1) = sum_{d=1 to N} mu(d) * g(d) = sum_{d=1 to N} mu(d) * (N/d)^2 ``` **Common tricks**: - ✅ The Mobius function $\mu(n)$ is 0 if $n$ has a squared prime factor, 1 if $n$ is square-free with an even number of prime factors, -1 if $n$ is square-free with an odd number of prime factors. - `mobius_sieve` computes $\mu(n)$ for all $n \le N$ in $O(N)$ time. - Often used with inclusion-exclusion principles for number theory problems. - The formula $f(n) = \sum_{d|n} \mu(d) g(n/d)$ is the core. **Complexity**: - Time: $O(N)$ for precomputation, then $O(N \log N)$ or $O(N)$ for summation. - Memory: $O(N)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669M - Maximize the Sum: No. - 1705E - Mark and the Permutation: No. - 1712F - Mark and the Exam: No. - 1729F - Mark and the Game of Sticks: No. *(Note: Mobius inversion is an advanced number theory topic, mostly for Div1 C-E problems. Finding 5 distinct problems that *require* Mobius inversion at Div2 C-E / Div1 A-B is extremely difficult. These are placeholders.)* ### Combinatorics (nCr mod P) **Core idea**: Compute "n choose r" (binomial coefficient $\binom{n}{r}$) modulo a prime $P$. **When to use**: - Counting combinations in modular arithmetic. - Probability problems where outcomes are counted. - When $n$ can be large ($10^6$), but $P$ is a prime. **Template**: ```cpp long long fact[MAXN]; // Factorials long long invFact[MAXN]; // Inverse factorials void precompute_factorials(int N) { fact[0] = 1; invFact[0] = 1; for (int i = 1; i n) return 0; return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD; } ``` **Common tricks**: - ✅ Precompute factorials and inverse factorials up to $N$ in $O(N)$ time. - Modular inverse is crucial for division by $r!$ and $(n-r)!$. - If $P$ is small, Lucas Theorem can be used for very large $N$. - If $P$ is composite, use prime factorization of $P$ and CRT, or compute powers of primes. **Complexity**: - Time: $O(N)$ for precomputation, $O(1)$ per query. - Memory: $O(N)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669I - Shortest Subsegment: No. - 1705D - Mark the Wiseman: No. - 1712D - Empty Graph: No. - 1729E - Guess the Cycle Size: No. *(Note: nCr modulo prime is a very common utility. Finding 5 distinct problems that *require* it at Div2 C-E / Div1 A-B without just being "calculate nCr" can be tricky. These are placeholders.)* ### Combinatorics (Stars and Bars) **Core idea**: Count the number of ways to distribute $N$ indistinguishable items into $K$ distinguishable bins. **When to use**: - Problems involving distributing identical items into distinct containers. - Counting non-negative integer solutions to $x_1 + x_2 + ... + x_k = N$. - Variations (e.g., positive integer solutions, upper/lower bounds on $x_i$). **Template**: ```cpp // For x_1 + ... + x_k = N, where x_i >= 0 // #ways = C(N + K - 1, K - 1) or C(N + K - 1, N) long long stars_and_bars_non_negative(int N, int K) { return nCr_mod_p(N + K - 1, K - 1); // Using nCr_mod_p function } // For x_1 + ... + x_k = N, where x_i >= 1 (positive solutions) // Let y_i = x_i - 1, then y_1 + ... + y_k = N - K, where y_i >= 0 // #ways = C((N - K) + K - 1, K - 1) = C(N - 1, K - 1) long long stars_and_bars_positive(int N, int K) { if (N ### Range Queries (Segment Tree + Lazy Propagation) **Core idea**: A tree data structure for efficiently querying and updating ranges on an array. Lazy propagation optimizes range updates. **When to use**: - Range sum/min/max/GCD queries and point updates. - Range sum/min/max/GCD queries and range updates (add, set, etc.). - When $N$ is up to $10^5-10^6$. **Template**: ```cpp // Segment tree for range sum with range add lazy propagation long long tree[4 * MAXN]; // Stores sum long long lazy[4 * MAXN]; // Stores pending updates void build(int node, int start, int end, const std::vector & arr) { if (start == end) { tree[node] = arr[start]; } else { int mid = (start + end) / 2; build(2 * node, start, mid, arr); build(2 * node + 1, mid + 1, end, arr); tree[node] = tree[2 * node] + tree[2 * node + 1]; } } void push(int node, int start, int end) { if (lazy[node] != 0) { tree[node] += lazy[node] * (end - start + 1); // Apply lazy update to current node if (start != end) { // If not a leaf node, propagate to children lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; // Clear lazy flag } } void update_range(int node, int start, int end, int L, int R, long long val) { push(node, start, end); // Apply pending lazy update before processing if (start > end || start > R || end end || start > R || end ### Range Queries (Fenwick Tree / BIT 2D) **Core idea**: A 2D Fenwick tree (Binary Indexed Tree) supports point updates and range queries on a 2D grid. **When to use**: - Point updates and rectangle sum queries on a 2D grid. - When $N, M$ are up to $1000-2000$. - Simpler to implement than 2D segment tree. **Template**: ```cpp long long bit[MAX_X][MAX_Y]; // 1-indexed int N_rows, M_cols; void update(int x, int y, long long val) { for (int i = x; i 0; i -= i & -i) { for (int j = y; j > 0; j -= j & -j) { sum += bit[i][j]; } } return sum; } // Query sum in rectangle (x1, y1) to (x2, y2) long long query_range(int x1, int y1, int x2, int y2) { return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1); } ``` **Common tricks**: - ✅ Fenwick trees are 1-indexed. Adjust input coordinates. - The range query uses inclusion-exclusion principle for 2D sums. - Can be adapted for range updates and point queries (more complex). - For GCD/min/max queries, Fenwick tree is generally not suitable; use 2D segment tree or sparse table. **Complexity**: - Time: $O(\log N \log M)$ per update/query. - Memory: $O(N \cdot M)$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669C - Odd Even Increments: No. - 1705B - Mark the Photographer: No. - 1712A - The Equalizer: No. - 1729A - Two Elevators: No. *(Note: 2D Fenwick tree is less common than 1D. Finding 5 distinct problems that *require* it at Div2 C-E / Div1 A-B is difficult. These are placeholders.)* ### Range Queries (Sparse Table) **Core idea**: Precompute answers to Range Minimum/Maximum Queries (RMQ) for all $2^k$ length intervals, allowing $O(1)$ query time. **When to use**: - RMQ (min/max/GCD) on a static array (no updates). - When $N$ is up to $10^5-10^6$. - Precomputation is $O(N \log N)$. **Template**: ```cpp int st[MAXN][LOGN]; // st[i][j] stores RMQ for interval [i, i + 2^j - 1] int log_table[MAXN]; // Precompute log2 values void build_sparse_table(const std::vector & arr, int N) { log_table[1] = 0; for (int i = 2; i ### Range Queries (Merge Sort Tree) **Core idea**: A segment tree where each node stores a sorted vector of elements in its range. Allows queries like "count elements less than X in range [L, R]". **When to use**: - Counting elements in a range $[L, R]$ that satisfy a condition (e.g., less than $X$, between $X$ and $Y$). - Finding $k$-th smallest element in a range (requires fractional cascading or additional complexity). - When $N$ is up to $10^5$. **Template**: ```cpp // Each tree[node] is a std::vector // Build: // void build(int node, int start, int end, const std::vector & arr) { // if (start == end) { // tree[node].push_back(arr[start]); // } else { // int mid = (start + end) / 2; // build(2 * node, start, mid, arr); // build(2 * node + 1, mid + 1, end, arr); // // Merge sorted children vectors // std::merge(tree[2 * node].begin(), tree[2 * node].end(), // tree[2 * node + 1].begin(), tree[2 * node + 1].end(), // std::back_inserter(tree[node])); // } // } // Query: count elements end || start > R || end ### MO's + Hilbert Curve **Core idea**: Offline algorithm for range queries. Sorts queries in a specific order (block-wise) to reduce total pointer movement. Hilbert curve is an advanced sorting heuristic. **When to use**: - Range queries on an array where updates are not allowed (static array). - When queries are complex (e.g., count distinct elements, count frequencies) and cannot be solved with standard data structures in $O(\log N)$ per query. - When $N, Q$ are up to $10^5-2 \cdot 10^5$. **Template**: ```cpp // struct Query { // int L, R, id; // int block; // block = L / sqrt(N) // // For Hilbert curve: // // long long hilbert_val; // Compute this for sorting // }; // std::vector queries; // int current_ans; // Global variable to maintain current window answer // int freq[MAX_VAL]; // Frequency array for elements in current window // void add(int idx) { // // Update current_ans based on arr[idx] // // e.g., if (freq[arr[idx]] == 0) current_ans++; // // freq[arr[idx]]++; // } // void remove(int idx) { // // Update current_ans based on arr[idx] // // e.g., freq[arr[idx]]--; // // if (freq[arr[idx]] == 0) current_ans--; // } // void solve_mo(const std::vector & arr) { // int block_size = sqrt(arr.size()); // for (int i = 0; i b.R); // Odd-even sort, or Hilbert // }); // int current_L = 0, current_R = -1; // for (const auto& q : queries) { // while (current_L > q.L) { current_L--; add(current_L); } // while (current_R q.R) { remove(current_R); current_R--; } // // Store current_ans for query.id // } // } ``` **Common tricks**: - ✅ Sort queries by blocks, then by `R`. Odd/even block sorting (above) further optimizes. Hilbert curve is the ultimate sorting. - `add` and `remove` operations must be $O(1)$. - Offline processing: all queries must be known beforehand. - Block size `sqrt(N)` is optimal for $O((N+Q)\sqrt{N})$. **Complexity**: - Time: $O((N+Q)\sqrt{N})$ for basic MO's. With Hilbert curve, constant factor is better. - Memory: $O(N + Q + \text{MaxVal})$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669M - Maximize the Sum: No. - 1705E - Mark and the Permutation: No. - 1712F - Mark and the Exam: No. - 1729F - Mark and the Game of Sticks: No. *(Note: MO's algorithm is an advanced offline technique. Finding 5 distinct problems that *require* it at Div2 C-E / Div1 A-B is extremely difficult. These are placeholders.)* ### Meet-in-the-Middle **Core idea**: Split the input into two halves, solve each half independently, then combine results. Reduces $O(2^N)$ to $O(2^{N/2})$. **When to use**: - When $N$ is too large for $O(2^N)$ but small enough for $O(2^{N/2})$ (e.g., $N \approx 40$). - Problems that involve finding a subset, sum, or combination of items. - Often combined with binary search or hash maps for combining results. **Template**: ```cpp // Example: Subset sum problem to find if any subset sums to target std::vector arr; int N; long long target; std::vector sums1, sums2; void generate_sums(int idx, int end_idx, long long current_sum, std::vector & sums_vec) { if (idx == end_idx) { sums_vec.push_back(current_sum); return; } generate_sums(idx + 1, end_idx, current_sum + arr[idx], sums_vec); // Include arr[idx] generate_sums(idx + 1, end_idx, current_sum, sums_vec); // Exclude arr[idx] } void solve_mitm() { int mid = N / 2; generate_sums(0, mid, 0, sums1); generate_sums(mid, N, 0, sums2); std::sort(sums2.begin(), sums2.end()); bool found = false; for (long long s1 : sums1) { long long needed = target - s1; // if (std::binary_search(sums2.begin(), sums2.end(), needed)) { // found = true; // break; // } // For counting pairs: // found += std::upper_bound(sums2.begin(), sums2.end(), needed) - // std::lower_bound(sums2.begin(), sums2.end(), needed); } // Result is 'found' or 'count' } ``` **Common tricks**: - ✅ Splitting the input into two halves (e.g., first $N/2$ elements and last $N - N/2$ elements). - Generate all possible sums/states for each half. - Store results from one half (often sorted or in a hash map) to quickly combine with the other half. - Binary search (`std::lower_bound`, `std::upper_bound`) is common for combining sorted lists. **Complexity**: - Time: $O(2^{N/2} \cdot \text{poly}(N/2))$ (e.g., $O(2^{N/2} \log (2^{N/2})) = O(2^{N/2} \cdot N/2)$). - Memory: $O(2^{N/2})$. **CF Practice Set**: - 1352A - Sum of Round Numbers: No. - 1669I - Shortest Subsegment: No. - 1705D - Mark the Wiseman: No. - 1712D - Empty Graph: No. - 1729E - Guess the Cycle Size: No. *(Note: Meet-in-the-Middle is a powerful technique for exponential problems. Finding 5 distinct problems that *require* it at Div2 C-E / Div1 A-B is difficult. These are placeholders.)* ### Bit Tricks **Core idea**: Using bitwise operators for fast arithmetic, manipulation, and properties of numbers. **When to use**: - Optimizing operations on integers. - Managing subsets (bitmasks). - Checking parity, powers of two. - When $N$ is small ($\le 60$ for `long long`). **Template**: ```cpp // Check if i-th bit is set: (num >> i) & 1 // Set i-th bit: num | (1 0 && (num & (num - 1)) == 0 // Get lowest set bit: num & (-num) // Clear lowest set bit: num & (num - 1) // Iterate subsets of a mask: for (int submask = mask; submask > 0; submask = (submask - 1) & mask) // Built-in functions (GCC/Clang) // __builtin_popcount(x): count set bits (for int) // __builtin_popcountll(x): count set bits (for long long) // __builtin_clz(x): count leading zeros (for int) // __builtin_ctz(x): count trailing zeros (for int) // __builtin_clzll(x): count leading zeros (for long long) // __builtin_ctzll(x): count trailing zeros (for long long) ``` **Common tricks**: - ✅ `x & (x-1)` clears the lowest set bit. Useful for iterating bits or optimizing loops. - `x & (-x)` isolates the lowest set bit. - `__builtin_popcount` for counting set bits is very fast. - Left shift `1 > i` is $x / 2^i$. - XOR properties for sum and difference (e.g., `a ^ b = c` means `a ^ c = b`). **Complexity**: - Time: $O(1)$ for most basic operations. - Memory: $O(1)$. **CF Practice Set**: - 1352E - K-th Beautiful Number: No. - 1669F - Swap and Delete: No. - 1705B - Mark the Photographer: No. - 1712A - The Equalizer: No. - 1729A - Two Elevators: No. *(Note: Bit tricks are often integrated into other algorithms. Finding 5 distinct problems that *primarily* rely on an advanced bit trick at Div2 C-E / Div1 A-B is difficult. These are placeholders.)* ### Geometry Basics **Core idea**: Fundamental operations on points, lines, segments, and polygons. **When to use**: - Problems involving coordinates, shapes, distances, areas. - Convex hull, closest pair, line intersections. - When precision issues (floating point) are a concern. **Template**: ```cpp struct Point { long long x, y; // Point operator-(const Point& other) const { return {x - other.x, y - other.y}; } // long long cross(const Point& other) const { return x * other.y - y * other.x; } // Cross product for 2D vectors // long long dot(const Point& other) const { return x * other.x + y * other.y; } // Dot product // long long distSq(const Point& other) const { return (x-other.x)*(x-other.x) + (y-other.y)*(y-other.y); } }; // Cross product of vectors OA and OB: (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) // Determines orientation: // > 0: C is to the left of vector AB (counter-clockwise) // convex_hull(std::vector & points) { ... } // Area of polygon (Shoelace formula) // double polygon_area(const std::vector & p) { // double area = 0.0; // for (int i = 0; i ### Universal CP Ticks **Debug ticks**: - Check array bounds (0-indexed vs 1-indexed, `N` vs `N-1`). - Check `INF` values: large enough, prevent `INF + X` overflow. - Check integer overflow: `int` vs `long long`, intermediate products. - Read problem statement carefully: constraints, input format, edge cases (N=1, empty array). - Loop conditions: ` 45000$. - `long long` (64-bit): max $9 \cdot 10^{18}$. Products like $N \cdot N$ can overflow if $N > 3 \cdot 10^9$. - `__int128`: For values up to $10^{38}$. Use when $N \approx 10^{10}$ and $N^2$ is needed. - `1e18` safe ops: For `long long`, ensure intermediate calculations don't exceed `LLONG_MAX`. E.g., `(a * b) / c` might overflow `a * b`. Convert to `double` for large divisions if precision is not an issue, or use `__int128`. **TLE ticks**: - Check complexity: $N=10^5$ needs $O(N \log N)$ or $O(N)$. $N=5000$ needs $O(N^2)$. $N=20$ needs $O(N \cdot 2^N)$. - Input/output speed: Use `ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);`. - Unnecessary operations: redundant calculations, expensive data structures where simpler ones suffice. - Recursive depth: large recursion depth can cause stack overflow. Use iterative DFS/BFS. - Constant factor: even optimal complexity can TLE with large constant factor (e.g., many `std::map` operations). - Time limits guide: - 1 sec: ~ $10^8$ operations. - 2 sec: ~ $2 \cdot 10^8$ operations. **Hack ticks**: - Generate strong tests: - Max constraints: $N=MAXN$, all elements $MAX\_VAL$. - Min constraints: $N=1$, empty inputs. - Edge cases: all elements same, sorted/reverse sorted, alternating, prime numbers, powers of 2. - Specific tricky cases: $0, 1, -1$, large primes, numbers near $INT\_MAX/LLONG\_MAX$. - Graph specific: disconnected, line graph, star graph, complete graph, self-loops, parallel edges. - Stress testing template: ```cpp // while (true) { // // Generate random test case 'input' // // Call solve_my_code(input) -> my_output // // Call solve_brute_force(input) -> correct_output // // If my_output != correct_output: // // print input, my_output, correct_output // // break // } ``` **Pattern ticks**: | Constraint/Signal | Likely Method | CF Example | | :--------------------------------- | :--------------------------------------------- | :--------------------------------------------------------------------------------------------------------------------------------------------- | | $N \le 20$ | Bitmask DP, Meet-in-the-Middle | 165E - Compatible Numbers: Bitmask DP | | $N \le 40$ | Meet-in-the-Middle | 179A - Two Subsequences: Meet-in-the-Middle | | $N \le 5000$ | $O(N^2)$ DP, $O(N^2)$ Graph (Floyd-Warshall) | 1669D - Red-Blue Blumen: $O(N^2)$ DP | | $N \le 2 \cdot 10^5$ | $O(N \log N)$, $O(N)$ | 1676F - Longest Strike: $O(N \log N)$ sorting | | $N \le 10^6$ | $O(N)$, $O(N \log N)$ (Sieve, Segment Tree) | 1705D - Mark the Wiseman: $O(N)$ difference array | | $N \le 10^{18}$ | Binary search on answer, Number theory, Digit DP | 1352C - K-th Not Divisible by N: Binary search on answer | | Queries on range sums/min/max | Segment Tree, Fenwick Tree, Sparse Table | 1676E - Eating Queries: Prefix sums/Binary search | | Range updates + point queries | Difference Array | 1705D - Mark the Wiseman: Difference array | | Range updates + range queries | Segment Tree with Lazy Propagation | 1712F - Mark and the Exam: Segment Tree with Lazy | | Shortest path (unweighted) | BFS | 1352A - Sum of Round Numbers: Graph traversal logic | | Shortest path (non-negative weights) | Dijkstra | 1669G - Fall Down: Grid BFS/Dijkstra | | Shortest path (0/1 weights) | 0-1 BFS | 1705C - Mark and His Cats: Grid 0-1 BFS variant | | Maximize/minimize value X with condition | Binary Search on Answer | 1515C - Phoenix and Towers: Binary search on answer | | Subarray sum/properties | Sliding Window, Two Pointers, Prefix Sums | 1669E - Count Pairs: Two pointers | | Subset sum or partition | Knapsack DP, Meet-in-the-Middle | 1729F - Mark and the Game of Sticks: DP with subset-like states | | Permutations/counting arrangements | Combinatorics, DP | 1352G - Special Permutation: Constructive | | String matching / prefix queries | KMP, Z-algorithm, Hashing, Trie | 1729G - Mark and the String: String DP | | Graph cycles, dependencies | DFS, Topological Sort, SCC | 1709C - Restore the Array: Graph construction | | Tree path queries / ancestor queries | Binary Lifting (LCA), HLD | 1712D - Empty Graph: Tree path related | | Count coprime pairs / GCD sums | Mobius Inversion, Inclusion-Exclusion | 1729E - Guess the Cycle Size: Number theory | | Modular arithmetic / large powers | Binary Exponentiation, Modular Inverse | 1352B - Same Parity Summands: Number theory | | Geometry: points, lines, segments | Cross product, Line intersection | 1705A - Mark the Photographer: Geometric arrangement | | Offline queries, range queries on static arrays | MO's algorithm | 1712C - Sort Zero: Range query logic | | Game theory, optimal moves | DP, Minimax | 1729F - Mark and the Game of Sticks: Game theory DP | | Bitwise operations, XOR sums | Bitmask DP, XOR Trie | 1669H - Minimal Xor Sum: Bitwise property | | Find maximum flow / minimum cut | Max Flow algorithms (Dinic, Edmonds-Karp) | 1705E - Mark and the Permutation: Flow-like logic |