Meta Title (60 characters)

C++ Competitive Programming Tutorial: Fast IO to Bit Tricks

Meta Description (159 characters)

Master C++ competitive programming with Fast IO, macros, templates, complexity analysis, bit manipulation, and mathematical algorithms using code.

Search Keywords

C++ Competitive Programming, Fast IO, C++ Macros, Templates, Time Complexity, Bit Manipulation, Competitive Programming Math, CP Tutorial, STL, C++ Algorithms

Module 32: Competitive Programming in C++

Introduction

Competitive Programming (CP) is the practice of solving algorithmic problems under strict time and memory constraints. It combines data structures, algorithms, mathematics, and optimization techniques to produce efficient solutions.

Popular competitive programming platforms include:

• Codeforces
• CodeChef
• AtCoder
• LeetCode
• HackerRank
• CSES
• UVa Online Judge

This module introduces the essential techniques every competitive programmer should know.

Learning Objectives

After completing this module, you will understand:

• Fast Input/Output
• Macros
• Function Templates
• Complexity Analysis
• Bit Manipulation
• Mathematical Algorithms
• Competitive Programming Tips

Competitive Programming Workflow

textCopy
1Read Input
2
3↓
4
5Choose Algorithm
6
7↓
8
9Optimize Complexity
10
11↓
12
13Write Code
14
15↓
16
17Submit
18
19↓
20
21Accepted

1. Fast Input/Output

Large inputs can make programs slow if standard I/O is not optimized.

Fast IO Setup

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    ios::sync_with_stdio(false);
7    cin.tie(nullptr);
8
9    int n;
10
11    cin >> n;
12
13    cout << n;
14
15    return 0;
16}

Why use it?

textCopy
1Without Fast IO
2
3Input → Slow
4
5With Fast IO
6
7Input → Fast

Reading Multiple Numbers

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    ios::sync_with_stdio(false);
7    cin.tie(nullptr);
8
9    int n;
10
11    cin >> n;
12
13    long long sum = 0;
14
15    for(int i = 0; i < n; i++)
16    {
17        int x;
18        cin >> x;
19        sum += x;
20    }
21
22    cout << sum;
23}

2. Macros

Macros reduce repetitive code.

Common CP Macros

cppCopy
1#include <iostream>
2#include <vector>
3using namespace std;
4
5#define ll long long
6#define pb push_back
7#define all(x) (x).begin(), (x).end()
8
9int main()
10{
11    vector<int> numbers;
12
13    numbers.pb(10);
14    numbers.pb(20);
15
16    cout << numbers.size();
17}

Output

textCopy
12

Loop Macro

cppCopy
1#include <iostream>
2using namespace std;
3
4#define FOR(i,a,b) for(int i=a;i<b;i++)
5
6int main()
7{
8    FOR(i,1,6)
9        cout << i << " ";
10}

Output

textCopy
11 2 3 4 5

3. Function Templates

Templates allow writing generic code.

cppCopy
1#include <iostream>
2using namespace std;
3
4template<typename T>
5T maximum(T a, T b)
6{
7    return (a > b) ? a : b;
8}
9
10int main()
11{
12    cout << maximum(10,20) << endl;
13    cout << maximum(4.5,3.8);
14}

Output

textCopy
120
24.5

Generic Swap

cppCopy
1#include <iostream>
2using namespace std;
3
4template<typename T>
5void swapValues(T& a, T& b)
6{
7    T temp = a;
8    a = b;
9    b = temp;
10}
11
12int main()
13{
14    int x = 5;
15    int y = 10;
16
17    swapValues(x,y);
18
19    cout << x << " " << y;
20}

Output

textCopy
110 5

4. Complexity Analysis

Competitive programming requires selecting algorithms with acceptable complexity.

Example

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int n = 100;
7
8    for(int i = 0; i < n; i++)
9        cout << i << " ";
10}

Time Complexity

textCopy
1O(n)

Nested Loops

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int n = 5;
7
8    for(int i = 0; i < n; i++)
9    {
10        for(int j = 0; j < n; j++)
11            cout << "* ";
12    }
13}

Time Complexity

textCopy
1O(n²)

5. Bit Manipulation

Bits allow very fast operations.

textCopy
113
2
3↓
4
51101₂

Check Odd or Even

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int n = 17;
7
8    if(n & 1)
9        cout << "Odd";
10    else
11        cout << "Even";
12}

Output

textCopy
1Odd

Set a Bit

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int x = 8;
7
8    x |= (1 << 1);
9
10    cout << x;
11}

Output

textCopy
110

Clear a Bit

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int x = 15;
7
8    x &= ~(1 << 2);
9
10    cout << x;
11}

Output

textCopy
111

Toggle a Bit

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int x = 10;
7
8    x ^= (1 << 1);
9
10    cout << x;
11}

Output

textCopy
18

Count Set Bits

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int x = 29;
7
8    cout << __builtin_popcount(x);
9}

Output

textCopy
14

Check Power of Two

cppCopy
1#include <iostream>
2using namespace std;
3
4bool isPowerOfTwo(int n)
5{
6    return n > 0 && (n & (n - 1)) == 0;
7}
8
9int main()
10{
11    cout << isPowerOfTwo(16);
12}

Output

textCopy
11

6. Mathematics

Many CP problems involve number theory and modular arithmetic.

Greatest Common Divisor (GCD)

cppCopy
1#include <iostream>
2#include <numeric>
3using namespace std;
4
5int main()
6{
7    cout << gcd(48,18);
8}

Output

textCopy
16

Least Common Multiple (LCM)

cppCopy
1#include <iostream>
2#include <numeric>
3using namespace std;
4
5int main()
6{
7    cout << lcm(12,18);
8}

Output

textCopy
136

Prime Number Check

cppCopy
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5bool isPrime(int n)
6{
7    if(n < 2)
8        return false;
9
10    for(int i = 2; i <= sqrt(n); i++)
11    {
12        if(n % i == 0)
13            return false;
14    }
15
16    return true;
17}
18
19int main()
20{
21    cout << isPrime(29);
22}

Output

textCopy
11

Fast Exponentiation (Binary Exponentiation)

Time Complexity: O(log n)

cppCopy
1#include <iostream>
2using namespace std;
3
4long long power(long long a,long long b)
5{
6    long long result = 1;
7
8    while(b > 0)
9    {
10        if(b & 1)
11            result *= a;
12
13        a *= a;
14        b >>= 1;
15    }
16
17    return result;
18}
19
20int main()
21{
22    cout << power(2,10);
23}

Output

textCopy
11024

Modular Exponentiation

cppCopy
1#include <iostream>
2using namespace std;
3
4const long long MOD = 1000000007;
5
6long long modPower(long long a,long long b)
7{
8    long long result = 1;
9
10    while(b)
11    {
12        if(b & 1)
13            result = (result * a) % MOD;
14
15        a = (a * a) % MOD;
16
17        b >>= 1;
18    }
19
20    return result;
21}
22
23int main()
24{
25    cout << modPower(2,20);
26}

Output

textCopy
11048576

Useful STL for Competitive Programming

cppCopy
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6int main()
7{
8    vector<int> numbers = {5,2,8,1};
9
10    sort(numbers.begin(), numbers.end());
11
12    for(int x : numbers)
13        cout << x << " ";
14}

Output

textCopy
11 2 5 8

Competitive Programming Template

cppCopy
1#include <bits/stdc++.h>
2using namespace std;
3
4#define ll long long
5#define fastio ios::sync_with_stdio(false); cin.tie(nullptr)
6
7int main()
8{
9    fastio;
10
11    int t;
12    cin >> t;
13
14    while(t--)
15    {
16        // Solve one test case
17    }
18
19    return 0;
20}

Note: <bits/stdc++.h> is supported by GCC and Clang but is not part of the C++ standard. For portable code, include only the headers you need.

Complexity Cheat Sheet

Real-World Applications

Best Practices

• Always enable Fast IO for large inputs.
• Analyse time complexity before coding.
• Prefer STL algorithms such as std::sort() and std::lower_bound().
• Use long long when integer overflow is possible.
• Use bit operations for performance-critical tasks.
• Test edge cases such as empty inputs, one element, and maximum constraints.

Common Mistakes

Using int Instead of long long

Large values may overflow a 32-bit integer.

Ignoring Constraints

Always match the algorithm's complexity to the problem limits.

Overusing Macros

Macros can reduce readability and make debugging harder. Prefer constexpr, using, or inline functions where appropriate.

Interview Questions

1. What is Fast IO in C++?

A technique that speeds up standard input and output using ios::sync_with_stdio(false); and cin.tie(nullptr);.

2. Why is time complexity important?

It estimates how an algorithm's running time grows as the input size increases, helping choose efficient solutions.

3. What is the advantage of templates?

Templates allow writing reusable, type-independent functions and classes.

4. What is bit manipulation?

Using bitwise operators (&, |, ^, ~, <<, >>) to perform efficient low-level operations.

5. How do you check whether a number is a power of two?

By verifying n > 0 && (n & (n - 1)) == 0.

6. What is binary exponentiation?

An algorithm that computes powers in O(log n) time by repeatedly squaring the base.

7. Why is 10^9 + 7 commonly used?

Because 1,000,000,007 is a large prime number that helps prevent overflow and supports modular arithmetic properties.

8. Which STL function sorts a container?

std::sort() from the <algorithm> header.

Module Summary

In this module, you learned:

• How to speed up input and output using Fast IO
• Using macros and templates to reduce repetitive code
• Analysing algorithm complexity
• Performing efficient bit manipulation
• Solving mathematical problems with GCD, LCM, prime testing, and binary exponentiation
• Using the C++ Standard Library effectively in competitive programming
• Building a reusable competitive programming template

These techniques form the foundation for solving programming contest problems efficiently and are widely used in coding interviews, online judges, and algorithm competitions.