C++ Performance for CP

Optimizing C++14 code involves managing memory directly, using fast I/O, and understanding template structures to minimize constant factors and avoid performance bottlenecks in competitive programming scenarios.

Advanced Tree Algorithms

Advanced tree problems are solved by decomposing them into linear structures using techniques like Heavy-Light Decomposition or by enabling fast path queries with binary lifting for LCA.

NTT & Generating Functions

Number Theoretic Transform (NTT) enables fast polynomial multiplication in modular arithmetic, crucial for solving complex counting problems using generating functions without floating-point precision errors.

Advanced Graph Algorithms

Network flow and matching problems are solved efficiently with algorithms like Dinic's and Hopcroft-Karp, which require careful management of residual graphs and cache-friendly data structures.

Debugging Advanced Algorithms

Effective debugging in competitive programming combines local stress testing against brute-force solutions, using macros for logging, and writing robust code to prevent common issues like integer overflow.

Synthesizing & Adapting Templates

Success in advanced problems requires composing modular templates, like combining Heavy-Light Decomposition with a Segment Tree, and adapting them to specific problem constraints for an optimal solution.

C++ Performance for CP

1. Fast I/O is crucial: ios_base::sync_with_stdio(false); cin.tie(NULL); prevents C++ streams from syncing with C streams, drastically speeding up input and output operations.
2. Global arrays over std::vector: For fixed-size or maximum-size constraints, global arrays avoid the overhead of dynamic memory allocation and potential reallocations that std::vector might incur.
3. Memory model matters: The C++14 memory model impacts how data is accessed. Cache-friendly layouts (like contiguous arrays) are faster than pointer-chasing structures (like std::list or node-based trees).
4. Constant-factor optimization wins contests: Small tweaks, like using int instead of long long where possible or pre-calculating values, can make the difference between TLE and AC.
5. Template logic flow: Competitive programming templates are designed for speed, often sacrificing some readability for minimal execution time by using global variables and concise macros.

Advanced Tree Algorithms

1. Binary lifting for LCA: Pre-computes ancestors at powers of 2 for each node, allowing any LCA query in $O(log N)$ time after an $O(N log N)$ preprocessing step.
2. HLD transforms tree paths: Heavy-Light Decomposition breaks a tree into paths (chains) that can be stored in a linear data structure like a Segment Tree, enabling path queries and updates.
3. Centroid Decomposition: Recursively finds the centroid of a tree and removes it, breaking the problem into smaller subproblems on the remaining subtrees. This is a divide-and-conquer approach.
4. Path queries become range queries: With HLD, a query on a path between two nodes u and v is converted into a set of range queries on the Segment Tree.
5. RMQ for LCA: An alternative to binary lifting, reducing the LCA problem to a Range Minimum Query on the tree's Euler tour, offering $O(1)$ query time after $O(N log N)$ preprocessing.

NTT & Generating Functions

1. NTT requires a prime modulus: The modulus P must be of the form $c \cdot 2^k + 1$ (a proth prime) to ensure the existence of a primitive root of unity, which is essential for the transform.
2. Iterative NTT is faster: An iterative implementation of NTT with bit-reversal permutation is generally faster and uses less stack memory than a recursive one.
3. Butterfly operation: This is the core calculation step in the Fast Fourier Transform (and NTT), combining results from smaller subproblems to build the final transform.
4. Generating functions encode sequences: A sequence of numbers $a_0, a_1, a_2, ...$ can be represented as a polynomial $A(x) = a_0 + a_1x + a_2x^2 + ...$, turning convolution problems into polynomial multiplication.
5. Modular inverse for division: Division in NTT (the inverse transform) is performed by multiplying by the modular multiplicative inverse of the sequence length N.

Advanced Graph Algorithms

1. Dinic's algorithm uses a level graph: It builds a layered network using BFS to find augmenting paths from source to sink, then uses DFS to push as much flow as possible through that level graph.
2. Residual graph tracks capacity: After pushing flow, capacities are updated in a residual graph. An edge u -> v with capacity c and flow f becomes a forward edge of capacity c-f and a backward edge v -> u of capacity f.
3. Hopcroft-Karp for bipartite matching: Finds the maximum matching in a bipartite graph faster than standard augmenting path algorithms. It finds multiple augmenting paths in a single phase.
4. Cache-friendly adjacency lists: Using arrays (head/next pointers) to implement an adjacency list is often faster than std::vector<std::vector<int>> due to better memory locality.
5. Blocking flow is key: In Dinic's, a blocking flow is found in each phase, which is a flow where every path from source to sink has at least one saturated edge in the level graph.

Debugging Advanced Algorithms

1. Stress test with a brute-force solution: Generate thousands of small, random test cases and compare the output of your advanced algorithm with a simple, correct (but slow) solution.
2. Use #ifdef LOCAL macros: Wrap debug print statements in #ifdef LOCAL ... #endif. This allows you to compile a verbose version for local testing and a clean version for submission without changing code.
3. Guard against integer overflow: When multiplying two long long integers under a modulus, cast to a 128-bit integer (__int128_t) or use modular multiplication functions to prevent overflow.
4. Correctness verification: For transforms like NTT, check correctness by performing the inverse transform and ensuring you get the original sequence back.
5. Profile hotspots: If getting TLE, use simple timing code to measure which parts of your algorithm (e.g., I/O, pre-computation, main loop) are taking the most time.

Synthesizing & Adapting Templates

1. Templates are a starting point: Never just copy-paste. Understand how to modify a template for different constraints, like changing the modulus in an NTT or handling edge weights in HLD.
2. Compose data structures: Many problems require combining algorithms. A common pattern is HLD on a tree, with a Segment Tree on the resulting linear paths to handle range queries.
3. Adapt for specific constraints: If a problem's constraints are small, a simpler algorithm might be better. If memory is tight, you might need to change your data structures.
4. From node problems to edge problems: Decompositions like HLD often work on nodes. To solve problems on edges, you may need to map each edge to the deeper of its two nodes.
5. The goal is modularity: Well-written templates have modular components (e.g., SegTree, NTT, LCA) that can be easily extracted and combined to build a solution for a new, complex problem.

Global Array: A fixed-size array declared outside any function, residing in static memory for the program's entire duration.

• Used in context: For a problem with up to $10^5$ nodes, we declare int adj[100005]; as a global array to avoid std::vector overhead.
• Don't confuse with: std::vector, which is a dynamic array that can grow and shrink at runtime.
• Topic: C++ Performance for CP

Fast I/O: A C++ optimization that decouples C++ iostreams from C's stdio library to accelerate input and output operations.

• Used in context: Adding ios_base::sync_with_stdio(false); cin.tie(NULL); is the first step for any competitive programming template to enable fast I/O.
• Topic: C++ Performance for CP

Binary Lifting: A technique used on trees to answer queries about ancestors in logarithmic time by pre-calculating the 2^i-th ancestor for every node.

• Used in context: We used binary lifting to find the LCA of nodes u and v in $O(log N)$ time.
• Don't confuse with: Simple parent pointers, which would take $O(N)$ time in the worst case.
• Topic: Advanced Tree Algorithms

Heavy-Light Decomposition (HLD): A tree decomposition technique that partitions the edges into 'heavy' and 'light' to break the tree into vertex-disjoint paths, useful for path queries.

• Used in context: With HLD, we can update all nodes on the path from the root to v by updating a few ranges in our segment tree.
• Topic: Advanced Tree Algorithms

Centroid: A node in a tree which, if removed, splits the tree into subtrees where each subtree has at most half the nodes of the original tree.

• Used in context: The centroid decomposition algorithm recursively finds and processes the centroid of the tree.
• Topic: Advanced Tree Algorithms

Number Theoretic Transform (NTT): A variant of the Fast Fourier Transform (FFT) that performs convolutions in a finite field, avoiding floating-point precision issues.

• Used in context: To multiply two large polynomials representing combinations, we use NTT with a suitable prime modulus.
• Don't confuse with: FFT, which uses complex numbers and is prone to precision errors.
• Topic: NTT & Generating Functions

Generating Function: A formal power series whose coefficients encode a sequence of numbers, used to solve counting and combinatorics problems.

• Used in context: The generating function for the Fibonacci sequence helps us find a closed-form expression for the n-th term.
• Topic: NTT & Generating Functions

Bit-Reversal Permutation: An operation that reorders an array by reversing the bits of its indices, used as the first step in iterative FFT and NTT algorithms.

• Used in context: Before the butterfly operations, we apply a bit-reversal permutation to the coefficient array.
• Topic: NTT & Generating Functions

Dinic's Algorithm: A strongly polynomial algorithm for computing the maximum flow in a network by repeatedly finding blocking flows in a level graph.

• Used in context: We used Dinic's algorithm to find the maximum amount of data that could be sent from the source to the sink.
• Topic: Advanced Graph Algorithms

Residual Graph: A graph representing the remaining capacity for flow between nodes in a network, including backward edges to allow 'undoing' flow.

• Used in context: After pushing 5 units of flow from u to v, the residual graph showed a new edge from v to u with capacity 5.
• Topic: Advanced Graph Algorithms

Stress Testing: The process of testing a program with a large number of generated random inputs to find edge cases or flaws in the algorithm's logic.

• Used in context: My HLD solution passed the sample cases, but failed during stress testing due to an off-by-one error in path queries.
• Topic: Debugging Advanced Algorithms

Modular Composition: The practice of building a complex algorithm by combining simpler, self-contained algorithmic components or data structures.

• Used in context: The solution required modular composition: we used HLD on the tree and then a Fenwick tree on each heavy path.
• Topic: Synthesizing & Adapting Templates

❌ MISTAKE: Using std::endl instead of "\n" for new lines in competitive programming.

• Why it happens: std::endl is taught as the standard way to end a line in C++, but it also forces a flush of the output buffer.
• ✅ Instead: Use cout << "\n";. This simply prints a newline character without the costly flush operation, which is critical for performance when printing many lines.
• Topic: C++ Performance for CP

❌ MISTAKE: Integer overflow when multiplying two long long integers in modular arithmetic.

• Why it happens: If a and b are both close to the modulus M, their product a * b can exceed the maximum value of a long long before the modulo operation is applied.
• ✅ Instead: Use a 128-bit integer type for the intermediate multiplication: (long long)((__int128_t)a * b % M);. This ensures the intermediate product does not overflow.
• Topic: Debugging Advanced Algorithms

❌ MISTAKE: Forgetting to handle both node and edge updates/queries in Heavy-Light Decomposition.

• Why it happens: A standard HLD template handles node values. If the problem asks for values on edges, a mapping is needed.
• ✅ Instead: Map each edge's value to the deeper of its two endpoint nodes. When querying a path, query the nodes as usual but exclude the value of the LCA's parent to avoid double-counting.
• Topic: Advanced Tree Algorithms

❌ MISTAKE: Choosing an incorrect or non-prime modulus for Number Theoretic Transform (NTT).

• Why it happens: The mathematics of NTT relies on a prime modulus of the form $P = c \cdot 2^k + 1$ to guarantee the existence of primitive roots of unity.
• ✅ Instead: Always use a well-known NTT-friendly prime, such as 998244353. Using a random prime will lead to incorrect results.
• Topic: NTT & Generating Functions

❌ MISTAKE: Incorrectly managing the residual graph in flow algorithms.

• Why it happens: Forgetting to add or update the backward edge after pushing flow is a common bug. The backward edge is what allows the algorithm to 'change its mind' and reroute flow.
• ✅ Instead: When pushing f units of flow from u to v, always decrease capacity of (u, v) by f and increase capacity of the backward edge (v, u) by f.
• Topic: Advanced Graph Algorithms

Dinic's Algorithm for Max Flow

Goal: Find the maximum flow from a source node s to a sink node t.

Step 1: Build Level Graph

• What happens: Run a Breadth-First Search (BFS) starting from the source s on the residual graph. The distance to each node from s is its 'level'.
• Key indicator: The BFS completes. If the sink t is unreachable, the algorithm terminates.
• Common error: Using edges with zero residual capacity in the BFS.

Step 2: Find Blocking Flow

• What happens: Run a Depth-First Search (DFS) from the source s, only moving to nodes v from u if level[v] == level[u] + 1.
• Key indicator: The DFS pushes as much flow as possible along paths in the level graph until no more augmenting paths can be found from s to t in the current level graph.
• Common error: Incorrectly terminating the DFS or mismanaging pointer-based adjacency lists to skip dead ends.

Step 3: Augment Flow & Update Residual Graph

• What happens: Add the total blocking flow found in Step 2 to the overall max flow. Update the capacities in the residual graph based on the flow pushed.
• Key indicator: The capacities of forward edges decrease, and backward edges increase.
• Common error: Forgetting to update the backward edge, which prevents the algorithm from finding optimal paths.

Step 4: Repeat

• What happens: Go back to Step 1 and repeat the process of building a new level graph and finding a blocking flow. The algorithm terminates when the sink t is no longer reachable from the source s in the level graph.

Visual flow: Initialize Flow = 0 → Loop { Build Level Graph → If sink not reachable, break → Find Blocking Flow → Augment Total Flow } → Return Total Flow

Topic: Advanced Graph Algorithms

Heavy-Light Decomposition (HLD) Query

Goal: Answer a query (e.g., sum, max) on the path between nodes u and v.

Step 1: Pre-computation

• What happens: Perform a DFS to calculate subtree sizes. Perform a second DFS to decompose the tree, identify heavy/light edges, assign nodes to chains, and compute their positions in a linear array for the Segment Tree.
• Key indicator: Each node has a chain_head, position_in_array, and parent.
• Common error: Incorrectly identifying the heavy child.

Step 2: Ascend to Same Chain

• What happens: While u and v are in different chains, move the node in the lower chain up. Query the path from its chain head to itself, and then move the node to the parent of its chain head.
• Key indicator: The node with the deeper chain_head is moved up.
• Common error: Moving the wrong node up or an off-by-one error in the Segment Tree query range.

Step 3: Final Same-Chain Query

• What happens: Once u and v are in the same chain, the remaining path is contiguous in the Segment Tree's base array.
• Key indicator: chain_head[u] == chain_head[v].
• Common error: Swapping u and v incorrectly, leading to an invalid query range.

Step 4: Combine Results

• What happens: Combine the results from all the Segment Tree queries performed in Steps 2 and 3 to get the final answer for the entire path.

Visual flow: Pre-computation (DFS) → While u,v in different chains { Query path u_chain_head..u → u = parent[u_chain_head] } → Query final path u..v → Combine Results

Topic: Advanced Tree Algorithms

↓

↓

Topic: NTT & Generating Functions