🚀 Essential C++ Templates for Competitive Programming 🚀

Mastering competitive programming requires not only a deep understanding of algorithms and data structures but also efficiency in implementing them during contests. Using template-based coding techniques can save valuable time and help you focus on problem-solving. Here's a collection of commonly used C++ templates that every competitive programmer should have in their toolkit.

1️⃣ Basic Competitive Programming Template

The foundation for most competitive programming solutions starts with a clean, fast I/O setup and common utility definitions.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
const int MOD = 1e9 + 7;

int main() {
    fastio;  // Fast input/output setup
    // Start coding your solution here
    return 0;
}        

Key Highlights:

• #include <bits/stdc++.h> imports everything in a single line.
• Macros for long types (ll), fast input/output (fastio), and constants (MOD).

2️⃣ Modulo Arithmetic

In many problems, you are asked to work with large numbers and return answers modulo a given constant (e.g., 1e9+7). Here's a simple template for modulo arithmetic.

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return (a * b) % MOD; }

ll mod_pow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = mod_mul(res, a);
        a = mod_mul(a, a);
        b >>= 1;
    }
    return res;
}        

Why It's Useful:

• Efficiently handles large numbers that require modulo operations, especially for combinatorial problems.
• mod_pow is frequently used in problems that need fast exponentiation.

3️⃣ Binary Search Algorithm

Binary search is one of the most efficient algorithms for searching in sorted arrays. It’s a must-have template for competitive programmers.

int binary_search(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;  // Target found
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;  // Target not found
}        

Where to Use:

• Problems that involve searching in sorted arrays.
• Variations can be used for solving monotonic functions or optimization problems.

4️⃣ Sieve of Eratosthenes (Prime Number Generation)

Sieve of Eratosthenes is an efficient algorithm to generate all prime numbers up to a given number n.

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;  // Mark multiples as non-prime
            }
        }
    }
    return is_prime;
}        

Use Case:

• Ideal for problems requiring prime number checking or generation, especially for large n (up to 10^6 or more).

5️⃣ Union-Find (Disjoint Set Union - DSU)

Union-Find is a crucial data structure for dynamic connectivity problems. It’s perfect for tasks like detecting cycles, connected components, and more.

class UnionFind {
    vector<int> parent, rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int u) {
        if (u == parent[u]) return u;
        return parent[u] = find(parent[u]);  // Path compression
    }

    void unite(int u, int v) {
        int root_u = find(u);
        int root_v = find(v);
        if (root_u != root_v) {
            if (rank[root_u] > rank[root_v]) parent[root_v] = root_u;
            else if (rank[root_u] < rank[root_v]) parent[root_u] = root_v;
            else {
                parent[root_v] = root_u;
                rank[root_u]++;
            }
        }
    }
};        

Where to Apply:

• Problems involving graph connectivity, MST (Minimum Spanning Tree), and dynamic connected components.

6️⃣ Dynamic Programming (0/1 Knapsack)

The 0/1 Knapsack problem is one of the most classic dynamic programming problems. The following template solves the problem in O(n * W) where n is the number of items and W is the capacity of the knapsack.

int knapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];  // Max value we can carry
}        

When to Use:

• Resource allocation problems where you need to decide what to include based on a maximum limit, such as knapsack, subset sum, and partition problems.

7️⃣ Topological Sort (Kahn’s Algorithm)

Topological sort is used for problems involving task scheduling, dependency resolution, or any problem based on Directed Acyclic Graphs (DAGs).

vector<int> topological_sort(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> in_degree(n, 0), topo_sort;
    queue<int> q;

    // Calculate in-degree of all vertices
    for (int i = 0; i < n; i++) {
        for (int v : adj[i]) {
            in_degree[v]++;
        }
    }

    // Add vertices with in-degree 0 to the queue
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) q.push(i);
    }

    // Process vertices
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_sort.pb(u);

        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) q.push(v);
        }
    }

    return topo_sort;
}        

Why It’s Important:

• Crucial for solving problems involving dependencies like job/task scheduling, resolving build orders, or determining prerequisites.

8️⃣ Trie for Prefix-Based Search

Tries (prefix trees) are highly efficient for solving string-based problems, especially those involving prefix searches or dictionary lookups.

struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;
    
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

class Trie {
    TrieNode* root;

public:
    Trie() { root = new TrieNode(); }

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) node->children[index] = new TrieNode();
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) return false;
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};        

Use Case:

• Highly efficient for auto-complete, prefix-matching, and string-related problems in contests.

These are just a few of the must-know C++ templates for competitive programming. Whether you're aiming to speed up your submissions or sharpen your problem-solving efficiency, having these templates at your disposal can make a significant difference.

🔗 #CompetitiveProgramming #CPlusPlusTemplates #CodingEfficiency #AlgorithmTemplates

This template-based approach can streamline your coding process in contests, giving you more time to focus on solving