🧰 The CP Toolkit

This is your battle-tested arsenal of code snippets. Every template here has been used in actual contests. Copy, paste, adapt, and win.

Pro Tip: Create a local file with all these snippets. Before each contest, have it open in a separate tab. During contest, Ctrl+F the pattern you need.

⚡ Lightning Round Snippets

Fast I/O Template

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

void solve() {
    // Your solution here
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

🔢 Math Snippets

GCD and LCM

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// C++17 has __gcd and you can use:
// ll g = __gcd(a, b);

Modular Arithmetic

const ll MOD = 1e9 + 7;

ll mod(ll x) { return ((x % MOD) + MOD) % MOD; }
ll add(ll a, ll b) { return mod(mod(a) + mod(b)); }
ll sub(ll a, ll b) { return mod(mod(a) - mod(b)); }
ll mul(ll a, ll b) { return mod(mod(a) * mod(b)); }

ll power(ll base, ll exp, ll m = MOD) {
    ll result = 1;
    base %= m;
    while (exp > 0) {
        if (exp & 1) result = mul(result, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return result;
}

ll modInverse(ll a) { return power(a, MOD - 2); }
ll divide(ll a, ll b) { return mul(a, modInverse(b)); }

nCr with Precomputation

const int MAXN = 2e5 + 5;
ll fact[MAXN], inv_fact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = mul(fact[i-1], i);
    
    inv_fact[MAXN-1] = modInverse(fact[MAXN-1]);
    for (int i = MAXN-2; i >= 0; i--)
        inv_fact[i] = mul(inv_fact[i+1], i+1);
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return mul(fact[n], mul(inv_fact[r], inv_fact[n-r]));
}

Prime Check and Sieve

bool isPrime(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// Sieve of Eratosthenes
const int MAXN = 1e6 + 5;
bool is_prime[MAXN];
vector<int> primes;

void sieve() {
    fill(is_prime, is_prime + MAXN, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < MAXN; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = (ll)i * i; j < MAXN; j += i)
                is_prime[j] = false;
        }
    }
}

📝 Array/Vector Snippets

Prefix Sum

// Build prefix sum
vector<ll> prefix(n + 1, 0);
for (int i = 0; i < n; i++)
    prefix[i + 1] = prefix[i] + a[i];

// Range sum [l, r] (0-indexed)
ll rangeSum(int l, int r) {
    return prefix[r + 1] - prefix[l];
}

Coordinate Compression

vector<int> a(n);
// ... read a

vector<int> sorted_a = a;
sort(all(sorted_a));
sorted_a.erase(unique(all(sorted_a)), sorted_a.end());

// Compress
for (int& x : a) {
    x = lower_bound(all(sorted_a), x) - sorted_a.begin();
}
// Now a[i] ∈ [0, unique_count - 1]

Kadane’s Algorithm (Max Subarray Sum)

ll maxSubarraySum(vector<ll>& a) {
    ll maxSum = LLONG_MIN, currentSum = 0;
    for (ll x : a) {
        currentSum = max(x, currentSum + x);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

Count Inversions (Merge Sort)

ll merge_count(vector<int>& arr, int l, int mid, int r) {
    vector<int> left(arr.begin() + l, arr.begin() + mid + 1);
    vector<int> right(arr.begin() + mid + 1, arr.begin() + r + 1);
    
    ll inv = 0;
    int i = 0, j = 0, k = l;
    
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
            inv += (left.size() - i);  // All remaining left elements are > right[j]
        }
    }
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
    
    return inv;
}

ll countInversions(vector<int>& arr, int l, int r) {
    ll inv = 0;
    if (l < r) {
        int mid = l + (r - l) / 2;
        inv += countInversions(arr, l, mid);
        inv += countInversions(arr, mid + 1, r);
        inv += merge_count(arr, l, mid, r);
    }
    return inv;
}

🔍 Binary Search Templates

Lower Bound (First ≥ target)

int lowerBound(vector<int>& a, int target) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // First index where a[i] >= target
}

Upper Bound (First > target)

int upperBound(vector<int>& a, int target) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // First index where a[i] > target
}

Binary Search on Answer

// Check if 'mid' is achievable
bool canAchieve(int mid) {
    // Problem-specific logic
    return true;
}

int binarySearchAnswer() {
    int lo = 0, hi = 1e9;  // Adjust bounds
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canAchieve(mid)) hi = mid;  // Find minimum
        // if (canAchieve(mid)) lo = mid + 1;  // Find maximum (then return lo - 1)
        else lo = mid + 1;
    }
    return lo;
}

Binary Search on Real Numbers

double binarySearchReal(double lo, double hi) {
    for (int iter = 0; iter < 100; iter++) {  // ~10^-30 precision
        double mid = (lo + hi) / 2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    return lo;
}

📐 Graph Snippets

Graph Representation

int n, m;  // nodes, edges
vector<vector<int>> adj(n + 1);  // Adjacency list

// For weighted graphs:
vector<vector<pair<int, int>>> adj(n + 1);  // {neighbor, weight}

// Read edges:
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);  // Remove for directed graph
}

DFS

vector<bool> visited(n + 1, false);

void dfs(int node) {
    visited[node] = true;
    // Process node
    
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

BFS (Shortest Path Unweighted)

vector<int> bfs(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    
    dist[start] = 0;
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
            }
        }
    }
    return dist;
}

Dijkstra’s Algorithm

vector<ll> dijkstra(int start) {
    vector<ll> dist(n + 1, LINF);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Union-Find (DSU)

class DSU {
public:
    vector<int> parent, rank_;
    
    DSU(int n) : parent(n + 1), rank_(n + 1, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // Path compression
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        return true;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

Topological Sort (Kahn’s Algorithm)

vector<int> toposort(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n + 1, 0);
    for (int u = 1; u <= n; u++)
        for (int v : adj[u])
            indegree[v]++;
    
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indegree[i] == 0)
            q.push(i);
    
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        
        for (int v : adj[u]) {
            if (--indegree[v] == 0)
                q.push(v);
        }
    }
    
    // order.size() == n means valid topo order exists
    return order;
}

🌳 Tree Snippets

Tree Diameter (Two BFS)

pair<int, int> farthest(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    
    int farthestNode = start, maxDist = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
                
                if (dist[neighbor] > maxDist) {
                    maxDist = dist[neighbor];
                    farthestNode = neighbor;
                }
            }
        }
    }
    return {farthestNode, maxDist};
}

int treeDiameter() {
    auto [u, _] = farthest(1);
    auto [v, diameter] = farthest(u);
    return diameter;
}

LCA with Binary Lifting

const int LOG = 20;
vector<int> depth(n + 1);
vector<vector<int>> up(n + 1, vector<int>(LOG));

void dfs_lca(int node, int parent) {
    up[node][0] = parent;
    for (int i = 1; i < LOG; i++)
        up[node][i] = up[up[node][i-1]][i-1];
    
    for (int child : adj[node]) {
        if (child != parent) {
            depth[child] = depth[node] + 1;
            dfs_lca(child, node);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    
    int diff = depth[a] - depth[b];
    for (int i = 0; i < LOG; i++)
        if ((diff >> i) & 1)
            a = up[a][i];
    
    if (a == b) return a;
    
    for (int i = LOG - 1; i >= 0; i--)
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    
    return up[a][0];
}

📊 DP Snippets

0/1 Knapsack

int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

Longest Increasing Subsequence (LIS)

int lis(vector<int>& a) {
    vector<int> dp;  // Stores smallest tail of LIS of each length
    
    for (int x : a) {
        auto it = lower_bound(dp.begin(), dp.end(), x);
        if (it == dp.end()) dp.push_back(x);
        else *it = x;
    }
    return dp.size();
}

Coin Change (Min Coins)

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

Edit Distance

int editDistance(string& a, string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
    }
    return dp[n][m];
}

📚 Data Structure Snippets

Segment Tree (Point Update, Range Query)

class SegmentTree {
    vector<ll> tree;
    int n;
    
    void build(vector<ll>& a, int node, int start, int end) {
        if (start == end) {
            tree[node] = a[start];
        } else {
            int mid = (start + end) / 2;
            build(a, 2*node, start, mid);
            build(a, 2*node+1, mid+1, end);
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
    
    void update(int node, int start, int end, int idx, ll val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) update(2*node, start, mid, idx, val);
            else update(2*node+1, mid+1, end, idx, val);
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
    
    ll query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query(2*node, start, mid, l, r) + 
               query(2*node+1, mid+1, end, l, r);
    }
    
public:
    SegmentTree(vector<ll>& a) {
        n = a.size();
        tree.resize(4 * n);
        build(a, 1, 0, n-1);
    }
    
    void update(int idx, ll val) { update(1, 0, n-1, idx, val); }
    ll query(int l, int r) { return query(1, 0, n-1, l, r); }
};

Binary Indexed Tree (Fenwick Tree)

class BIT {
    vector<ll> tree;
    int n;
    
public:
    BIT(int n) : n(n), tree(n + 1, 0) {}
    
    void update(int i, ll delta) {
        for (++i; i <= n; i += i & (-i))
            tree[i] += delta;
    }
    
    ll query(int i) {  // Sum [0, i]
        ll sum = 0;
        for (++i; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }
    
    ll query(int l, int r) {  // Sum [l, r]
        return query(r) - (l ? query(l - 1) : 0);
    }
};

🔀 String Snippets

String Hashing

const ll BASE = 31, MOD = 1e9 + 9;
vector<ll> pw, h;

void buildHash(string& s) {
    int n = s.size();
    pw.resize(n + 1);
    h.resize(n + 1);
    
    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = (pw[i-1] * BASE) % MOD;
    
    h[0] = 0;
    for (int i = 0; i < n; i++)
        h[i+1] = (h[i] * BASE + s[i] - 'a' + 1) % MOD;
}

ll getHash(int l, int r) {  // Hash of s[l..r]
    return (h[r+1] - h[l] * pw[r - l + 1] % MOD + MOD) % MOD;
}

KMP Pattern Matching

vector<int> computeLPS(string& pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);
    
    int len = 0, i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else if (len) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

vector<int> kmpSearch(string& text, string& pattern) {
    vector<int> lps = computeLPS(pattern);
    vector<int> matches;
    
    int n = text.size(), m = pattern.size();
    int i = 0, j = 0;
    
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++; j++;
            if (j == m) {
                matches.push_back(i - j);
                j = lps[j - 1];
            }
        } else if (j) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return matches;
}

🔀 Bit Manipulation Snippets

// Check if ith bit is set
bool isSet(int n, int i) { return (n >> i) & 1; }

// Set ith bit
int setBit(int n, int i) { return n | (1 << i); }

// Clear ith bit
int clearBit(int n, int i) { return n & ~(1 << i); }

// Toggle ith bit
int toggleBit(int n, int i) { return n ^ (1 << i); }

// Count set bits
int countBits(int n) { return __builtin_popcount(n); }
int countBitsLL(ll n) { return __builtin_popcountll(n); }

// Lowest set bit
int lowestBit(int n) { return n & (-n); }

// Check if power of 2
bool isPowerOf2(int n) { return n && !(n & (n - 1)); }

// Iterate over all subsets of mask
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // Process subset 'sub'
}

Keep this toolkit handy. Before every contest, skim through it. The more familiar these patterns become, the faster you’ll code during contests.Copy. Paste. Win. 🏆

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

​🧰 The CP Toolkit

​⚡ Lightning Round Snippets

​Fast I/O Template

​🔢 Math Snippets

​GCD and LCM

​Modular Arithmetic

​nCr with Precomputation

​Prime Check and Sieve

​📝 Array/Vector Snippets

​Prefix Sum

​Coordinate Compression

​Kadane’s Algorithm (Max Subarray Sum)

​Count Inversions (Merge Sort)

​🔍 Binary Search Templates

​Lower Bound (First ≥ target)

​Upper Bound (First > target)

​Binary Search on Answer

​Binary Search on Real Numbers

​📐 Graph Snippets

​Graph Representation

​DFS

​BFS (Shortest Path Unweighted)

​Dijkstra’s Algorithm

​Union-Find (DSU)

​Topological Sort (Kahn’s Algorithm)

​🌳 Tree Snippets

​Tree Diameter (Two BFS)

​LCA with Binary Lifting

​📊 DP Snippets

​0/1 Knapsack

​Longest Increasing Subsequence (LIS)

​Coin Change (Min Coins)

​Edit Distance

​📚 Data Structure Snippets

​Segment Tree (Point Update, Range Query)

​Binary Indexed Tree (Fenwick Tree)

​🔀 String Snippets

​String Hashing

​KMP Pattern Matching

​🔀 Bit Manipulation Snippets

🧰 The CP Toolkit

⚡ Lightning Round Snippets

Fast I/O Template

🔢 Math Snippets

GCD and LCM

Modular Arithmetic

nCr with Precomputation

Prime Check and Sieve

📝 Array/Vector Snippets

Prefix Sum

Coordinate Compression

Kadane’s Algorithm (Max Subarray Sum)

Count Inversions (Merge Sort)

🔍 Binary Search Templates

Lower Bound (First ≥ target)

Upper Bound (First > target)

Binary Search on Answer

Binary Search on Real Numbers

📐 Graph Snippets

Graph Representation

DFS

BFS (Shortest Path Unweighted)

Dijkstra’s Algorithm

Union-Find (DSU)

Topological Sort (Kahn’s Algorithm)

🌳 Tree Snippets

Tree Diameter (Two BFS)

LCA with Binary Lifting

📊 DP Snippets

0/1 Knapsack

Longest Increasing Subsequence (LIS)

Coin Change (Min Coins)

Edit Distance

📚 Data Structure Snippets

Segment Tree (Point Update, Range Query)

Binary Indexed Tree (Fenwick Tree)

🔀 String Snippets

String Hashing

KMP Pattern Matching

🔀 Bit Manipulation Snippets