Comprehensive Guide to the Competitive Programmer's Handbook (2018)

This document serves as a rewritten synthesis of the Competitive Programmer's Handbook, a foundational resource designed to transition programmers from basic coding to the high-performance world of competitive programming (CP).

1. The Foundation: Time and Space Complexity

In CP, the efficiency of an algorithm is paramount. We use Big O notation to describe the upper bound of an algorithm's running time.

Common Complexity Classes

The following table outlines the typical time complexities encountered:

Pro Tip: A general rule of thumb is that a typical online judge can handle roughly $10^8$ operations per second. If $n=10^5$, an $\mathcal{O}(n^2)$ algorithm will likely result in a Time Limit Exceeded (TLE) error.

---

2. Mastering C++ for CP

C++ is the preferred language for CP due to its speed and the powerful Standard Template Library (STL).

Essential STL Components

• std::vector: A dynamic array.
• std::set / std::map: Balanced BSTs providing $\mathcal{O}(\log n)$ operations.
• std::priority_queue: Useful for Dijkstra's algorithm.
• std::sort: An efficient hybrid sorting algorithm.

Implementation Example

Below is a snippet demonstrating a basic fast-I/O setup and the use of a vector:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Speed up I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    
    sort(v.begin(), v.end());
    cout << "Sorted first element: " << v[0] << "\n";
    return 0;
}

---

3. Dynamic Programming (DP)

Dynamic Programming is the art of breaking a complex problem into smaller, overlapping subproblems and storing their results to avoid redundant calculations.

The DP Workflow

1. Define the state (e.g., dp[i] is the max value using $i$ elements).
2. Find the transition (the recurrence relation).
3. Identify the base cases.

State Transition Visualization

For a simple 1D DP problem (like climbing stairs), the state transition can be visualized as:

---

4. Graph Algorithms

Graphs are used to model networks, maps, and dependencies.

Core Traversal Techniques

• Breadth-First Search (BFS): Finds the shortest path in unweighted graphs.
• Depth-First Search (DFS): Useful for connectivity, cycle detection, and topological sorting.
• Dijkstra's Algorithm: Finds the shortest path in weighted graphs (non-negative edges).

Using DFS for shortest paths in unweighted graphs $\rightarrow$ Use BFS instead.

---

5. Mathematical Foundations

Competitive programming relies heavily on number theory and combinatorics.

Modular Arithmetic

Since answers can be very large, problems often ask for the result modulo $10^9 + 7$. The property of modular addition is: $(a + b) \pmod m = ((a \pmod m) + (b \pmod m)) \pmod m$

Greatest Common Divisor (GCD)

The Euclidean Algorithm is the standard for finding the GCD of two numbers: $\gcd(a, b) = \gcd(b, a \pmod b)$

---

6. Learning Roadmap

To master the content of the handbook, follow this checklist:

• Understand Big O and time limits.
• Master STL containers (vector, map, set).
• Implement Binary Search and Two Pointers.
• Solve 20+ DP problems (Knapsack, LCS).
• Implement BFS, DFS, and Dijkstra.
• Learn Segment Trees and Fenwick Trees for range queries.
• Study Modular Inverse and Combinatorics.

Summary of Range Query Tools