1. Fibonacci

Idea: Each number is the sum of the two before it.

0, 1, 1, 2, 3, 5, 8, 13, ...

fib[1] = 0, fib[2] = 1;
for (int i = 3; i <= n; i++) fib[i] = fib[i-1] + fib[i-2];

Trace for n=6:

fib[1] = 0
fib[2] = 1
fib[3] = fib[2] + fib[1] = 1+0 = 1
fib[4] = fib[3] + fib[2] = 1+1 = 2
fib[5] = fib[4] + fib[3] = 2+1 = 3
fib[6] = fib[5] + fib[4] = 3+2 = 5

Why DP? You reuse previously computed values instead of recalculating recursively every time.

2. Number of Ways (Staircase)

Problem: You're on step s, want to reach step e. Each move you can jump +1, +2, or +3 steps. How many ways?

dp[s] = 1;  // one way to be at start
for (int i = s+1; i <= e; i++) {
    if (i-1 >= s) dp[i] += dp[i-1];  // came from 1 step back
    if (i-2 >= s) dp[i] += dp[i-2];  // came from 2 steps back
    if (i-3 >= s) dp[i] += dp[i-3];  // came from 3 steps back
}

Trace for s=0, e=4:

dp[0] = 1
dp[1] = dp[0]           = 1
dp[2] = dp[1]+dp[0]     = 2
dp[3] = dp[2]+dp[1]+dp[0] = 4
dp[4] = dp[3]+dp[2]+dp[1] = 7

Intuition: To know how many ways to reach step i, just ask: how many ways were there to reach the 3 steps before it? Add them up.

3. Broken Steps

Problem: Same as above, but some steps are broken — you can't land on them.

if (broken[i]) continue;         // skip broken steps entirely
if (!broken[i-1] ...) dp[i] += dp[i-1];  // only add if that step is usable

Trace for s=0, e=4, broken={2}:

dp[0] = 1
dp[1] = dp[0] = 1
dp[2] → SKIP (broken)
dp[3] = dp[2](broken, skip) + dp[1] + dp[0] = 0+1+1 = 2
dp[4] = dp[3] + dp[2](broken=0) + dp[1] = 2+0+1 = 3

Key insight: A broken step contributes 0 ways because dp[broken] = 0 and we skip computing it. But we still need to avoid adding FROM broken steps, hence the !broken[i-k] checks.

4. LIS — Longest Increasing Subsequence

Problem: Given an array, find the length of the longest subsequence where each element is strictly greater than the previous.

Example:

[3, 1, 4, 1, 5, 9, 2, 6] → LIS is [1, 4, 5, 9] = length 4

dp[i] = 1;  // every element alone is a subsequence of length 1
for (int i = 0; i < n; i++)
    for (int o = 0; o < i; o++)
        if (s[o] < s[i])
            dp[i] = max(dp[i], dp[o] + 1);

Trace for [3, 1, 4, 2, 5]:

i=0: s[0]=3, dp[0]=1         → [3]
i=1: s[1]=1, nothing before is <1, dp[1]=1   → [1]
i=2: s[2]=4, s[0]=3<4 → dp[2]=dp[0]+1=2
              s[1]=1<4 → dp[2]=max(2,dp[1]+1)=2  → [1,4] or [3,4]
i=3: s[3]=2, s[1]=1<2 → dp[3]=dp[1]+1=2     → [1,2]
i=4: s[4]=5, s[0]=3<5 → dp[4]=2
              s[2]=4<5 → dp[4]=max(2,dp[2]+1)=3
              s[3]=2<5 → dp[4]=max(3,dp[3]+1)=3  → [1,4,5] or [1,2,5]

ans = max(1,1,2,2,3) = 3

Intuition: dp[i] = "what's the longest increasing subsequence that ends exactly at position i?" For each i, look back at all previous elements smaller than s[i] and extend the best one.

Link: https://cses.fi/problemset/task/1145

5. Grid Max Path

Problem: Given an n×m grid with values, start at top-left (1,1), reach bottom-right (n,m). You can only move right or down. Maximize the sum of values collected.

dp[1][1] = s[1][1];
// first column: can only come from above
for (int i = 2; i <= n; i++) dp[i][1] = dp[i-1][1] + s[i][1];
// first row: can only come from left
for (int i = 2; i <= m; i++) dp[1][i] = dp[1][i-1] + s[1][i];
// rest: come from above or left, pick better
for (int i = 2; i <= n; i++)
    for (int o = 2; o <= m; o++)
        dp[i][o] = max(dp[i-1][o], dp[i][o-1]) + s[i][o];

Trace for grid:

Grid:          dp table:
1  3  2        1   4   6
4  2  1  →     5   7   8
2  1  3        7   8  11

Step by step:

dp[1][1]=1, dp[1][2]=4, dp[1][3]=6
dp[2][1]=5, dp[3][1]=7
dp[2][2]=max(dp[1][2], dp[2][1])+2 = max(4,5)+2 = 7
dp[2][3]=max(dp[1][3], dp[2][2])+1 = max(6,7)+1 = 8
dp[3][2]=max(dp[2][2], dp[3][1])+1 = max(7,7)+1 = 8
dp[3][3]=max(dp[2][3], dp[3][2])+3 = max(8,8)+3 = 11

Intuition: Each cell can only be reached from the top or the left. Pick whichever path brought the higher sum, then add the current cell's value.

Link: https://cses.fi/problemset/task/1638 (or grid path variant)

6. Dice Combinations

Problem: How many ways can you make sum n by rolling a 6-sided die any number of times? Order matters — (1,2) and (2,1) are different.

dp[0] = 1;  // one way to make sum 0: roll nothing
for (int i = 1; i <= n; i++)
    for (int o = 1; o <= 6; o++)
        if (i - o >= 0)
            dp[i] += dp[i-o];   // mod 1e9+7

Trace for n=4:

dp[0] = 1
dp[1] = dp[0]                         = 1
dp[2] = dp[1]+dp[0]                   = 2
dp[3] = dp[2]+dp[1]+dp[0]             = 4
dp[4] = dp[3]+dp[2]+dp[1]+dp[0]       = 8

Intuition: To make sum i, the last die roll was some face o (1–6). Before that roll, the sum was i-o. So count all ways to make i-o and add them up. dp[0]=1 is the base — "empty sequence" has exactly one way.

Why mod 1e9+7? The numbers grow astronomically fast. Modulo keeps them from overflowing int.

Link: https://cses.fi/problemset/task/1633

The Universal DP Thought Process

Every DP problem follows the same 3 steps:

1. DEFINE  → what does dp[i] mean?
2. TRANSITION → how do I compute dp[i] from smaller values?
3. BASE CASE → what's the starting value I know for sure?

1. Minimum Coins (Coin Change)

Goal: Find the minimum number of coins needed to reach a given sum.

vector<int> dp(sum + 1, INT_MAX - 1);
dp[0] = 0;

for (int i = 1; i <= sum; i++) {
    for (auto it : s) {
        if (i - it >= 0)
            dp[i] = min(dp[i], dp[i - it] + 1);
    }
}

Idea: For every amount i, try using each coin. If using coin it improves the answer, update dp[i].

We always rely on a smaller subproblem dp[i - it] that is already computed.

2. Coin Combinations I — Order Matters

Goal: Count the number of ordered sequences of coins that sum to sum.

dp[0] = 1;

for (int i = 1; i <= sum; i++) {
    for (auto it : s) {
        if (i - it >= 0)
            dp[i] += dp[i - it];

        if (dp[i] >= 1e9 + 7)
            dp[i] -= 1e9 + 7;
    }
}

Key observation: Loop order is:

amount → coins

This means different orders are counted separately, so [1,3] and [3,1] are different solutions.

3. Coin Combinations II — Order Doesn't Matter

Goal: Count unordered combinations of coins.

dp[0] = 1;

for (auto it : s) {
    for (int i = 1; i <= sum; i++) {
        if (i - it >= 0)
            dp[i] += dp[i - it];

        if (dp[i] >= 1e9 + 7)
            dp[i] -= 1e9 + 7;
    }
}

Key observation: Loop order becomes:

coins → amount

Each coin is processed fully before moving to the next one, therefore permutations collapse into a single combination.

4. Removing Digits

Goal: Starting from n, repeatedly subtract one of its digits until reaching 0. Find the minimum number of steps.

vector<int> dp(n + 1, INT_MAX - 1);
dp[n] = 0;

for (int i = n; i >= 0; i--) {
    if (dp[i] == INT_MAX - 1) continue;

    int x = i;
    while (x) {
        int dig = x % 10;
        x /= 10;

        if (dig && i - dig >= 0)
            dp[i - dig] = min(dp[i - dig], dp[i] + 1);
    }
}

Important note: The loop must be i >= 0, not i >= n.

Idea: From every reachable number, try subtracting each of its digits and update the result if a shorter path is found.

5. Book Shop (0/1 Knapsack)

Goal: Maximize total pages without exceeding budget x. Each book can be chosen at most once.

int dp[100005] = {};

for (int i = 0; i < n; i++) {
    for (int o = x; o >= 1; o--) {
        if (o >= p[i])
            dp[o] = max(dp[o], dp[o - p[i]] + h[i]);
    }
}

Why iterate backwards?

Iterating from x downwards guarantees that every item is used only once. Forward iteration would allow reusing the same item multiple times (unbounded knapsack).

Quick Reference

In this blog, we discuss an implementation of Dijkstra's Algorithm to compute the shortest paths from a single source in a directed weighted graph with non-negative weights.

Problem Setting

We are given:

• n nodes (numbered from 1 to n)
• m directed edges
• Each edge has weight w ≥ 0

Goal: Find the shortest distance from node 1 to every other node.

Example

Input:

4 5
1 2 1
1 3 4
2 3 2
2 4 5
3 4 1

Output:

0 1 3 4

Explanation:

• Node 1 → Node 1: distance = 0
• Node 1 → Node 2: distance = 1 (direct edge)
• Node 1 → Node 3: distance = 3 (path: 1 → 2 → 3)
• Node 1 → Node 4: distance = 4 (path: 1 → 2 → 3 → 4)

When to Use Dijkstra

Use Dijkstra when:

• The graph is weighted
• All weights are non-negative
• You need shortest paths from a single source

Do NOT use Dijkstra when:

• Negative edge weights → use Bellman-Ford or SPFA
• All-pairs shortest paths → use Floyd-Warshall
• Unweighted graph → use BFS (O(n + m))
• Tree structure → use DFS/BFS

Core Idea

We use a min-priority queue to always process the node with the smallest current distance.

Key observation:

The first time we pop a node from the priority queue, we have already found its shortest distance.

So once a node is marked as visited (finalized), we never process it again.

Data Structures

• adj[u] — adjacency list storing (neighbor, weight)
• dis[i] — shortest distance to node i
• vis[i] — whether the node has been finalized
• priority_queue — min-heap ordered by distance

Important: In C++, priority_queue is a max-heap by default. We use greater<> to turn it into a min-heap.

Algorithm Steps

1. Push (0, start) into the priority queue.
2. While the queue is not empty:

• Extract the node with the smallest cost.
• If already visited, skip it.
• Mark it as visited.
• Fix its distance.
• Push all unvisited neighbors with updated cost.

1. Continue until the queue becomes empty.

Time Complexity: O((n + m) log n)

Implementation

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

#define ll long long
const int N = 2e5 + 5;

int n, m;
ll dis[N];
vector<pair<int,ll>> adj[N];
bool vis[N];

void dijkstra(int start)
{
    priority_queue<
        pair<ll,int>,
        vector<pair<ll,int>>,
        greater<pair<ll,int>>
    > pq;

    pq.push({0, start});

    while(!pq.empty())
    {
        auto p = pq.top();
        pq.pop();

        ll cost = p.first;
        int node = p.second;

        if(vis[node]) continue;

        vis[node] = true;
        dis[node] = cost;

        for(auto [next, weight] : adj[node])
        {
            if(!vis[next])
            {
                pq.push({cost + weight, next});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    dijkstra(1);

    for(int i = 1; i <= n; i++)
    {
        if(vis[i])
            cout << dis[i] << " ";
        else
            cout << -1 << " ";
    }
}

---

Practice Problems

Easy

• CSES – Shortest Routes I https://cses.fi/problemset/task/1671/

• Codeforces 20C – Dijkstra? https://codeforces.me/problemset/problem/20/C

Medium

• Codeforces 715B – Complete The Graph https://codeforces.me/problemset/problem/715/B

• AtCoder ABC362E – Count Arithmetic Subsequences https://atcoder.jp/contests/abc362/tasks/abc362_e

Hard

• Codeforces 464E – The Classic Problem https://codeforces.me/problemset/problem/464/E

BFS is one of the most important graph algorithms, especially when we want to find the shortest path in an unweighted graph.

Why BFS?

• DFS is not suitable for shortest path problems because it may go deep into one branch until reaching a leaf, even if a shorter path exists.
• BFS explores the graph level by level, which guarantees that the first time we reach a node, we reached it using the minimum number of edges.

How BFS works

• We use a queue
• Start from the source node
• Visit all neighbors (level 1)
• Then neighbors of neighbors (level 2), and so on

Queue order example:

X
x1  x2
x11 x12 x21 x22
x111 x112 x221 x222 ...

This level-by-level traversal is exactly why BFS gives the shortest path.

Key Idea for Shortest Path

• Store (node, distance)
• When we reach the destination node for the first time, that distance is the shortest path.

BFS Implementation

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

const int N = 1e5 + 5;
vector<int> adj[N];
bool vis[N];

int bfs(int start, int end) {
    queue<pair<int,int>> q;
    q.push({start, 0});
    vis[start] = true;

    while (!q.empty()) {
        auto [node, dist] = q.front();
        q.pop();

        if (node == end)
            return dist;

        for (int nxt : adj[node]) {
            if (!vis[nxt]) {
                vis[nxt] = true;
                q.push({nxt, dist + 1});
            }
        }
    }
    return -1; // no path
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    cout << bfs(1, 5);
}

Complexity

• Time: O(n + m)
• Space: O(n)

Final Notes (Blog Style Tips)

• BFS = shortest path in unweighted graphs
• DFS = exploring paths, not shortest
• Always mark visited when pushing to queue
• BFS is basically multi-source Dijkstra with weight = 1

Graph Representation

There are three main ways to represent graphs:

Adjacency List (Most Common)

int n, m;
cin >> n >> m;
vector<vector<pair<int,int>>> adj(n+1);
for(int i = 0, u, v, w; i < m; i++){
    cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w); // if undirected
}

Adjacency Matrix

int n, m;
cin >> n >> m;
vector<vector<int>> adj(n+1, vector<int>(n+1, -1));
for(int i = 0, u, v, w; i < m; i++){
    cin >> u >> v >> w;
    adj[u][v] = w;
    adj[v][u] = w; // if undirected
}

Edge List

vector<array<int,3>> edges(m);
for(auto &[u,v,w] : edges){
    cin >> u >> v >> w;
}

Basic DFS

Standard DFS Implementation

vector<vector<pair<int,int>>> adj;
vector<bool> vis;

void dfs(int u){
    cout << u << " ";
    vis[u] = true;
    for(auto [v, w] : adj[u]){
        if(!vis[v]){
            dfs(v);
        }
    }
}

Complete Setup

int n, m; 
cin >> n >> m;
adj.assign(n+1, {});
vis.assign(n+1, false);
for(int i = 0, u, v, w; i < m; i++){
   cin >> u >> v >> w;
   adj[u].emplace_back(v, w);
   adj[v].emplace_back(u, w);
}
dfs(1);

Connected Components

Count the number of separate components in an undirected graph.

int n, m; 
cin >> n >> m;
adj.assign(n+1, {});
vis.assign(n+1, false);

for(int i = 0, u, v; i < m; i++){
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
}

int components = 0;
for(int u = 1; u <= n; u++){
    if(!vis[u]){
        components++;
        dfs(u);
    }
}
cout << components << '\n';

Path Finding

Finding Path with Specific Conditions

vector<long long> path;
bool found = false;
long long tar;

void dfs(long long cur){
    if(cur > tar || found) return;
    
    path.push_back(cur);
    
    if(cur == tar){
        found = true;
        return;
    }
    
    dfs(cur * 2);
    dfs(cur * 10 + 1);
    
    if(!found)
        path.pop_back(); // backtrack
}

Finding Path from Leaf

unordered_map<long long, vector<long long>> adj;
unordered_map<long long, int> vis;
vector<long long> res;
unordered_map<long long, int> freq;

void dfs(long long u){
    vis[u] = 1;
    res.push_back(u);
    for(auto v : adj[u]){
        if(!vis[v]){  
            dfs(v);
        }
    }
}

// Find starting leaf (degree = 1)
long long start = -1;
for(auto it : freq){
    if(it.second == 1){
        start = it.first;
        break;
    }
}

dfs(start);
for(auto it : res){
    cout << it << " ";
}

Tree DFS

DFS on Tree (with Parent Tracking)

void dfsTree(int u, int par){
    for(auto [v, w] : adj[u]){
        if(v == par) continue;
        dfsTree(v, u);
    }
}

Finding Maximum Path to Leaf

int ans = 0;

void dfs(int par, int u, int sum){
    if(adj[u].size() == 1){ // leaf node
        ans = max(ans, sum);
    }
    for(auto [v, w] : adj[u]){         
        if(v != par){
            dfs(u, v, sum + w);    
        }
    }
}

Conditional Tree Traversal (e.g., Consecutive Cats Problem)

int ans = 0;
vector<int> cat;
int m;

void dfs(int u, int par, int consecutiveCats){
    if(cat[u] == 1)
        consecutiveCats++;
    else
        consecutiveCats = 0;

    if(consecutiveCats > m)
        return;

    int children = 0;
    for(int v : adj[u]){
        if(v != par){
            children++;
            dfs(v, u, consecutiveCats);
        }
    }
    
    if(children == 0){ // leaf
        ans++;
    }
}

Bipartite Checking

Check if a graph can be divided into two groups where no two nodes in the same group are connected.

Method 1: Using Depth Levels

unordered_map<int, vector<int>> adj;
map<int, int> ans;
map<int, int> vis;
int flag = 1;

void dfs(int u, int j){
    vis[u] = 1;
    ans[u] = (j % 2 == 1) ? 1 : 2;
    
    for(auto v : adj[u]){
        if(!vis[v]){
            dfs(v, j + 1);
        }
        else if(ans[v] == ans[u]){
            flag = 0;
            return;
        }
    }
}

Method 2: Using Color Array

int flag = 0;
unordered_map<int, int> color;

void dfs(int u, vector<vector<int>>& adj, map<int, int>& vis, int i){
    vis[u] = 1;
    color[u] = (i % 2 == 1) ? 1 : 2;
    
    for(auto v : adj[u]){
        if(!vis[v]){
            dfs(v, adj, vis, i + 1);
        }
        if(vis[v] && color[u] == color[v]){
            flag = 1;
            return;
        }
    }
}

// Check all components
for(int k = 1; k <= n; k++){
    if(!vis[k])
        dfs(k, adj, vis, 1);
}

Practice Problems

1. CSES — Counting Rooms

Problem: Count the number of rooms in a grid where # is wall and . is floor.

Key Idea: Mark all connected floor cells in the same room as visited. Each DFS call represents one room.

int n, m;
vector<vector<char>> vec;

void dfs(int i, int j){
    if(i >= n || j >= m || i < 0 || j < 0) return;
    if(vec[i][j] == '#' || vec[i][j] == 'v') return;
    
    if(vec[i][j] == '.'){
        vec[i][j] = 'v';
    }
    
    dfs(i+1, j);
    dfs(i-1, j);
    dfs(i, j+1);
    dfs(i, j-1);
}

int main(){
    cin >> n >> m;
    vec.resize(n, vector<char>(m));
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> vec[i][j];
    
    int rooms = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(vec[i][j] == '.'){
                rooms++;
                dfs(i, j);
            }
        }
    }
    
    cout << rooms << '\n';
}

2. CSES — Building Teams

Problem: Divide students into two teams such that no two friends are on the same team.

// Use the bipartite checking code from above
// If flag == 0, output "IMPOSSIBLE"
// Otherwise, output the team assignments from ans/color array

3. Finding Cycle in Graph

int ans = INT_MAX;
int n;

void dfs(int u, int par, int i, int c){
    for(auto [v, w] : adj[u]){
        if(v == 1){
            if(i + 1 == n){
                ans = min(ans, c + w);
            }
        }
        else if(v != par){
            dfs(v, u, i + 1, c + w);
        }
    }
}

Tips and Tricks

1. Always check visited status before recursing to avoid infinite loops
2. Use parent tracking in trees to avoid going back to parent
3. Backtracking: Remove from path when DFS returns unsuccessfully
4. Grid DFS: Check bounds first, then walls/visited, then mark visited
5. Multiple components: Loop through all nodes and DFS unvisited ones
6. Bipartite: Color nodes with alternating colors, check for conflicts

Complexity Analysis

• Time Complexity: O(V + E) where V is vertices and E is edges
• Space Complexity: O(V) for visited array and recursion stack

Happy Coding!

substr(a, b) → take part of the string

stoi(s) → convert string → int

to_string(x) → convert int → string

Tags: #math #number-theory #implementation #templates Difficulty: ★☆☆ — ★★☆ TL;DR: Treat every number as a multiset of prime powers (a “box of primes”).

• gcd = take minimum exponent for each prime.
• lcm = take maximum exponent for each prime.
• Use Euclid (%) for fast gcd.
• For modular division with prime modulus, use Fermat → inverse = pow(a, MOD-2).
• Generate all divisors by recursion over prime powers.

1) Numbers = Boxes of Prime Factors

Example:

• 12 = 2^2 * 3^1 → box: {2,2,3}
• 6 = 2^1 * 3^1 → multiplying by 6 is like adding 2 and 3 into the box.

If

• 24 = 2^3 * 3^1
• 30 = 2^1 * 3^1 * 5^1 then gcd(30,24) uses min exponents: 2^min(3,1)*3^min(1,1)*5^min(0,1) = 2^1 * 3^1 = 6. lcm uses max exponents: 2^3 * 3^1 * 5^1 = 120.

2) GCD — Properties & Implementation

Properties:

• gcd(a,b) = gcd(b,a%b) (Euclid)
• gcd(a,0) = a
• gcd(a,b) = gcd(a-b, b) (subtraction method — slow)

Example reduction: gcd(30,24) 30%24=6 → gcd(24,6) → 24%6=0 → gcd(6,0)=6

Fast C++ (Euclidean)

long long gcd(long long a, long long b){
    while(b){
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

Complexity: O(log(min(a,b))).

3) LCM — Use GCD to Avoid Overflow

Formula: lcm(a,b) = a / gcd(a,b) * b

long long lcm(long long a, long long b){
    if(a==0 || b==0) return 0;
    long long g = gcd(a,b);
    return (a / g) * b;
}

Complexity same as gcd.

4) Modular Arithmetic — Why and When

We use modular arithmetic to keep numbers small and prevent overflow, especially in competitive programming.

Reasons to Use It

1. Prevent overflow:

cpp long long a = 1e18, b = 1e18; long long c = a * b; // Overflow! long long c_mod = (a % MOD) * (b % MOD) % MOD; // Safe 2. Problem explicitly asks:

> Output the answer modulo 10^9+7 3. Fast combinatorics & number theory: factorials, powers, nCr etc. grow extremely fast. 4. Division modulo prime: requires modular inverse. 5. Cyclic/wrapping behavior: clocks, circular arrays, hashing.

Rules

• Only use modulo when required or to avoid overflow.
• All operations should be modulo MOD.
• Use modular inverse for division (not normal /).

Basic Operations

const ll MOD = 1e9+7;
ll add(ll a,ll b){ return (a%MOD + b%MOD) % MOD; }
ll sub(ll a,ll b){ return (a%MOD - b%MOD + MOD) % MOD; }
ll mul(ll a,ll b){ return (a%MOD * b%MOD) % MOD; }
ll powmod(ll a,ll e){ ... } // fast exponentiation
ll inv(ll a){ return powmod(a, MOD-2); } // division modulo prime
ll divide(ll a,ll b){ return mul(a, inv(b)); }

✅ Key idea: Modular arithmetic does not give the actual number, it gives the number modulo MOD, which is usually exactly what the problem expects.

5) Generating All Divisors

A) From prime factorization {(p_i, e_i)}

void gen_divisors_rec(int idx, ll cur,
                      const vector<pair<ll,int>>& fac,
                      vector<ll>& out){
    if(idx == fac.size()){ out.push_back(cur); return; }
    ll p = fac[idx].first;
    int e = fac[idx].second;
    ll val = 1;
    for(int k = 0; k <= e; ++k){
        gen_divisors_rec(idx+1, cur * val, fac, out);
        val *= p;
    }
}

B) From distinct primes (each exponent = 1)

void gen_from_primes(int idx, long long cur, 
                     const vector<long long>& primes,
                     vector<long long>& out){
    if(idx == primes.size()){ out.push_back(cur); return; }
    gen_from_primes(idx+1, cur, primes, out); // skip
    gen_from_primes(idx+1, cur * primes[idx], primes, out); // take
}

6) All-in-One Template

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;

ll gcdll(ll a, ll b){
    while(b){ ll t = a % b; a = b; b = t; }
    return a;
}
ll lcmll(ll a, ll b){ return (a / gcdll(a,b)) * b; }

ll mod_mul(ll a, ll b){ return ((a%MOD)*(b%MOD))%MOD; }
ll mod_pow(ll a, ll e){
    ll res=1; a%=MOD;
    while(e){
        if(e&1) res = mod_mul(res,a);
        a = mod_mul(a,a);
        e >>= 1;
    }
    return res;
}
ll mod_inv(ll x){ return mod_pow(x, MOD-2); }
ll mod_div(ll a, ll b){ return mod_mul(a, mod_inv(b)); }

void gen_divisors_rec(int idx, ll cur, const vector<pair<ll,int>>& fac, vector<ll>& out){
    if(idx == fac.size()){ out.push_back(cur); return; }
    ll p = fac[idx].first;
    int e = fac[idx].second;
    ll val = 1;
    for(int k=0;k<=e;++k){
        gen_divisors_rec(idx+1, cur * val, fac, out);
        val *= p;
    }
}

int main(){
    ll a = 30, b = 24;
    cout << "gcd("<<a<<","<<b<<") = "<< gcdll(a,b) << "\n";
    cout << "lcm("<<a<<","<<b<<") = "<< lcmll(a,b) << "\n";

    vector<pair<ll,int>> fac = {{2,3},{3,1}}; // 24
    vector<ll> divs;
    gen_divisors_rec(0,1,fac,divs);
    sort(divs.begin(), divs.end());
    cout << "divisors of 24: ";
    for(ll d : divs) cout << d << ' ';
    cout << "\n";
}

7) Common Pitfalls

• Overflow: use a / gcd(a,b) * b for lcm
• Division modulo prime: always use modular inverse
• Generating divisors: large exponents → many divisors → high memory/time

8) Practice Problems

• Compute gcd & lcm for multiple queries
• Count divisors from prime factorization
• Generate divisors and check properties (sum, range)
• Modular inverses & combinatorics

What is a Prime Number?

A prime is an integer strictly larger than one that is divisible only by one and by itself.

So to check whether n is prime or not, the basic idea is:

• Try all numbers from 2 → n-1
• If any number divides n, then n is composite
• Otherwise, n is prime

Naive Code

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Optimization: Why Only Check Until √n ?

Example: n = 16

Divisors:

• 1 × 16
• 2 × 8
• 4 × 4
• 8 × 2
• 16 × 1

Notice something?

After reaching 4 = sqrt(16), the divisors start repeating.

✔️ This means we only need to check divisibility up to sqrt(n).

Optimized Prime Check

#define ll long long

bool is_prime(ll n) {
    if (n <= 1) return false;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

The Sieve of Eratosthenes — O(n log log n)

Imagine numbers from 2 → 20:

1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16
17 18 19 20

Idea

1. Assume all numbers are prime
2. Start from 2
3. Eliminate all multiples of 2
4. Move to the next number that is still marked prime
5. Eliminate all its multiples
6. Continue…

At the end, all remaining true entries are primes.

Sieve Code

const int N = 1e6 + 5;
vector<bool> prime(N, true);

void sieve() {
    prime[0] = prime[1] = false;
    for (int i = 2; i * i < N; i++) {
        if (prime[i]) {
            for (int j = i * i; j < N; j += i) {
                prime[j] = false;
            }
        }
    }
}

Complexity Intuition

Removing all multiples of:

• 2 → n/2
• 3 → n/3
• 4 → n/4
• 5 → n/5
• …
• n → n/n

Total work:

n(1/2 + 1/3 + 1/4 + ... + 1/n) = n log(n)

But composite numbers contribute less, giving final:

Sieve = O(n log log n)

Get All Divisors of n in O(√n)

vector<ll> divisors(ll n) {
    vector<ll> ret;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i != n / i) ret.push_back(n / i);
        }
    }
    return ret;
}

Count Prime Divisors for All Numbers (Divisor Sieve)

const int N = 1e6 + 5;
int d[N];   // d[i] = number of prime divisors of i

void sieveDivisors() {
    for (int i = 2; i < N; i++) {
        if (d[i] == 0) {  // i is prime
            for (int j = i; j < N; j += i) {
                d[j]++;
            }
        }
    }
}

Prime Factorization in O(√n)

vector<pair<ll, ll>> primeFactors(ll n) {
    vector<pair<ll, ll>> ret;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            ret.push_back({i, cnt});
        }
    }
    if (n != 1) ret.push_back({n, 1});
    return ret;
}

Conclusion

You learned:

Basic prime checking

Optimizing with sqrt(n)

Sieve of Eratosthenes

Time complexity intuition

Getting divisors

Counting prime divisors

Prime factorization

--- https://codeforces.me/contest/2175/problem/A

Tip: Counting Distinct Elements in All Prefixes

When a problem asks for the number of distinct elements before or up to each index, use prefix traversal + frequency tracking.

Idea

• Traverse the array from left to right.
• Maintain a frequency map (or array).
• When an element appears for the first time, increase the distinct count.
• Store this count for each prefix.

Implementation

map<int, int> freq;
vector<int> distinct(n);
int cnt = 0;

for (int i = 0; i < n; i++) {
    if (++freq[x[i]] == 1)
        cnt++;              // new distinct element
    distinct[i] = cnt;      // distinct elements in prefix [0..i]
}

Sum of Distinct Counts Over All Prefixes

long long ans = 0;
for (int i = 0; i < n; i++) {
    ans += distinct[i];
}

Why This Works

Each element contributes to the distinct count exactly once, at its first occurrence.

--- https://codeforces.me/contest/2175/problem/B

Idea: Reconstruct the Array Using Prefix XOR

Sometimes we don’t know the array a directly, but we know how its prefix XOR array should look. In that case, the trick is:

1. Construct a valid prefix XOR array p
2. Recover the original array a from it

Key Observation

If [ p[i] = a[1] \oplus a[2] \oplus \dots \oplus a[i] ]

then: [ a[i] = p[i] \oplus p[i-1] ]

So once p is known, a is uniquely determined.

Constructing the Prefix Array p

We build an array p that represents how the prefix XOR of a should look:

• p[0] = 0
• For all indices:

• p[i] = i

• Except at position r, where p[r] = l - 1

int n, l, r;
cin >> n >> l >> r;

vector<int> p(n + 1);
p[0] = 0;

for (int i = 1; i <= n; i++) {
    if (i == r)
        p[i] = l - 1;
    else
        p[i] = i;
}

Recovering Array a

Using the XOR relation:

vector<int> a(n + 1);

for (int i = 1; i <= n; i++) {
    a[i] = p[i] ^ p[i - 1];
    cout << a[i] << " ";
}

Why This Works

• XOR is reversible.
• Knowing consecutive prefix values is enough to reconstruct the original array.
• This technique is very common in problems involving prefix XOR constraints.

--- Custom Comparator for Pairs: Sort by Sum Tip: Sort pairs in descending order based on sum of elements. Implementation: cpp sort(vec.begin(), vec.end(), [](const pair<int,int> &a, const pair<int,int> &b) { return (a.first + a.second) > (b.first + b.second); });

Check Parity: Same or Different Even/Odd Check if two numbers have different parity: cppif ((a ^ b) & 1) { // a and b have different parity (one even, one odd) }

--- // map struct cmp{ bool operator()(const pair<int,int>&a,const pair<int,int>&b)const{ if(a.first!=b.first) return a.first>b.first; return a.second<b.second;

} }; multiset<pair<int,int>,cmp>st;

Bitmasking is one of the most powerful and elegant techniques in competitive programming. It allows us to represent subsets using bits and perform complete search efficiently.

Complete Search → Iterative Approach

We can iterate over all subsets of a set of size n using integers from 0 to (1 << n) - 1.

Each bit in the number represents whether we include the element or not.

Difference Between Terms

Example

Suppose we have the array:

[1, 2, 5, 9]

Each bitmask from 0000 to 1111 (binary) represents a subset:

1 << n = (2^n) → total number of subsets.

Example 1: Count Subsequences with Sum = K

int n, k;  
cin >> n >> k;  
vector<int> a(n);
for (int &x : a) cin >> x;

int res = 0;

for (int mask = 0; mask < (1 << n); ++mask) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) {
            sum += a[i];
        }
    }
    if (sum == k) ++res;
}

cout << res;

We loop through all 2^n masks and check which subsets have a sum equal to k.

Example 2: Apple Division (CSES Problem)

Find the minimum difference between the total weights of two groups of apples.

int n;
cin >> n;
vector<int> a(n);
for (auto &i : a) cin >> i;

int mn = INT_MAX;

for (int mask = 0; mask < (1 << n); ++mask) {
    int g1 = 0, g2 = 0;
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) g1 += a[i];
        else g2 += a[i];
    }
    mn = min(mn, abs(g1 - g2));
}

cout << mn;

Bitset

A bitset is an array of bits (0 or 1). It is more memory-efficient and provides useful built-in functions.

#include <bitset>
bitset<62> b;

Useful Methods

Example

bitset<8> a = 5;   // 00000101
bitset<8> b = 9;   // 00001001

bitset<8> c = a | b;   // bitwise OR
cout << c << "\n";     // 00001101

cout << a[2] << "\n";  // access bit #2

a = ~a;                // bitwise NOT

Complexity

• Operations on a 64-bit bitset → O(64)
• Operations on a 32-bit bitset → O(32)

Summary

• Use bitmasking to represent subsets efficiently.
• Iterate from 0 to (1 << n) - 1 for complete search.
• Use bitset when you need fast operations on bits.
• Common use cases: subset sum, partitioning, combinatorial search.

Bitwise operations are one of the most powerful tricks in programming — especially in competitive programming — because they are fast (O(1)) and help us manipulate numbers efficiently.

Basics

All numbers are stored in binary form (0s and 1s) in memory.

Each bit has a value:

• 0 → OFF
• 1 → ON

The last bit in a signed integer represents the sign:

• 0 → Positive
• 1 → Negative (in two’s complement form → invert bits + add 1)

Common Bitwise Operators

&   AND        → bit is 1 if both bits are 1  
|   OR         → bit is 1 if any bit is 1  
^   XOR        → bit is 1 if bits are different  
~   NOT        → inverts all bits  
<<  Left Shift → multiply by 2^x  
>>  Right Shift→ divide by 2^x

Binary Representation

#include <bitset>
#include <iostream>
using namespace std;

int main() {
    int a = 5;
    cout << bitset<32>(a) << endl;     // Binary representation of a
    cout << bitset<32>(~a) << endl;    // Binary of NOT a
}

bitset<32> means we represent the number using 32 bits.

Turning Bits On / Off / Flip

Turn ON bit x Make sure bit x = 1 (keep others unchanged):

a = a | (1 << x);

Explanation: (1 << x) shifts 1 to the left by x positions, so it creates a number with only one bit ON at position x. Then, using the OR | operation turns that bit ON without changing the others.

Turn OFF bit x Make sure bit x = 0:

a = a & ~(1 << x);

Explanation: (1 << x) marks the bit you want to turn off. ~ inverts all bits (so that the bit you want to clear becomes 0, and all others are 1). Then & keeps all bits the same, except that bit x becomes 0.

Flip bit x If it’s 1 → 0, if it’s 0 → 1:

a = a ^ (1 << x);

Explanation: ^ (XOR) changes a bit only if the bits differ. So this toggles the target bit: 1 → 0, 0 → 1.

Check if bit x is ON

Two ways:

if (a & (1 << x)) cout << "ON";
else cout << "OFF";

or

if ((a >> x) & 1) cout << "ON";

Identity Elements

Identity for AND (&) → all bits = 1 as  (a & -1) = a   as (-1=1111111... )
Identity for OR (|)  → all bits = 0 as  (a | 0) = a    as (0=000000000.. )
Identity for XOR (^) → all bits = 0 as  (a ^ 0) = a    as (0=000000000.. )

Important XOR Properties

a ^ a = 0
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

Even / Odd Check

if (x & 1) cout << "Odd";
else cout << "Even";

Example: Can a string form a palindrome?

Idea: In a palindrome, every letter appears an even number of times — except possibly one. We use XOR to track whether each character appears an odd or even number of times.

string s;
cin >> s;
int ans = 0;

for (char c : s) {
    ans ^= 1 << (c - 'a');
}

// if at most one bit is ON → palindrome possible
if (ans == 0 || (ans & (ans - 1)) == 0)
    cout << "YES";
else
    cout << "NO";

Explanation of (ans & (ans - 1)) == 0: Example:

ans = 1000  
ans - 1 = 0111  
ans & (ans - 1) = 0000

This trick checks whether ans has only one bit ON (i.e., it’s a power of 2). If a number has just one set bit, subtracting 1 flips all bits after that position — so ans & (ans - 1) becomes 0. That’s why this condition means “at most one odd-count letter” → palindrome possible.

Built-in Bit Functions (GCC)

__builtin_popcount(x)    → Count 1s in integer
__builtin_popcountll(x)  → Count 1s in long long
__builtin_clz(x)         → Count leading zeros
__builtin_ctz(x)         → Count trailing zeros
__lg(x)                  → Position of the highest bit (≈ floor(log2(x)))

Explanation:

• __builtin_clz(x) → Counts how many zeros come before the first 1 from the left.
• __builtin_ctz(x) → Counts how many zeros come after the last 1 from the right. These are useful to find the position of the first or last set bit quickly.

Example

int x = 8;
cout << __builtin_popcount(x) << endl; // 1
cout << __lg(x) << endl;               // 3
cout << (1 << __lg(x)) << endl;        // 8

Summary

Turn ON bit: a = a | (1 << x)

Turn OFF bit: a = a & ~(1 << x)

Flip bit: a = a ^ (1 << x)

Check bit: (a >> x) & 1

Even / Odd: x & 1

Multiply by 2ˣ: a << x

Divide by 2ˣ: a >> x

All bitwise operations work in O(1). Mastering them can make your code shorter, faster, and smarter.

Some notes while solving:

XOR with 1 flips the last bit of a number. Even numbers end with 0, so it becomes 1 (the number increases by 1). Odd numbers end with 1, so it becomes 0 (the number decreases by 1).

Hi everyone! In this post I’ll try to make recursion clear using stack intuition and ASCII trees after each example.

What is Recursion?

A function can call another function. A function can also call itself — that’s recursion.

Example:

void Print2() {
    cout << "NOUR";
}

void Print() {
    Print2();
    cout << "NOUR";
}

int main() {
    Print();
}

Stack:

Push: main() → Print() → Print2()
Pop:  Print2() → Print() → main()

• exit(0) → terminates all stack frames immediately.
• return → terminates only the current function.

What if the function calls itself with no stop?

void Print() {
    Print();
    cout << "NOUR";
}

int main() {
    Print();
}

Stack:

Push: main() → Print() → Print() → Print() → … infinite
Pop:  never happens → program crashes (stack overflow)

We need a base case to stop recursion.

Adding a base case

int n = 5;

void Print(int i) {
    if (i == n) return; // base case
    Print(i + 1);       // recursive call with modified input
    cout << "NOUR";
}

int main() {
    Print(0);
}

Stack trace (push):

main() → Print(0) → Print(1) → Print(2) → Print(3) → Print(4) → return

Stack trace (pop):

Print(4) → Print(3) → Print(2) → Print(1) → Print(0) → main()

Everything after the recursive call waits until the recursive call finishes.

Example 1: Printing Digits of a Number

We want: 1234007 → 1 2 3 4 0 0 7

void digit(int x) {
    if (x == 0) return;
    digit(x / 10);
    cout << x % 10 << ' ';
}

int main() {
    digit(1234007);
}

Call tree:

digit(1234007)
 └─ digit(123400)
     └─ digit(12340)
         └─ digit(1234)
             └─ digit(123)
                 └─ digit(12)
                     └─ digit(1)
                         └─ digit(0)

Unwinding prints: 1 2 3 4 0 0 7

Example 2: Factorial

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

Call tree for fact(4):

fact(4)
 └─ 4 * fact(3)
      └─ 3 * fact(2)
           └─ 2 * fact(1)
                └─ 1 * fact(0)

During unwind:

fact(0)=1
fact(1)=1*1=1
fact(2)=2*1=2
fact(3)=3*2=6
fact(4)=4*6=24

Example 3: Fibonacci

int fibo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

int main() {
    cout << fibo(5);
}

Call tree for fibo(5):

fibo(5)
 ├─ fibo(4)
 │   ├─ fibo(3)
 │   │   ├─ fibo(2)
 │   │   │   ├─ fibo(1)
 │   │   │   └─ fibo(0)
 │   │   └─ fibo(1)
 │   └─ fibo(2)
 │       ├─ fibo(1)
 │       └─ fibo(0)
 └─ fibo(3)
     ├─ fibo(2)
     │   ├─ fibo(1)
     │   └─ fibo(0)
     └─ fibo(1)

Example 4: LIS (Longest Increasing Subsequence)

int n;
int s[20];

int LIS(int i, int last) {
    if (i == n) return 0;

    int ch1 = LIS(i + 1, last);
    int ch2 = 0;
    if (s[i] > last) {
        ch2 = 1 + LIS(i + 1, s[i]);
    }
    return max(ch1, ch2);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    cout << LIS(0, -1);
}

For array [3,1,2] recursion tree (take or not take):

LIS(0,-∞)
 ├─ skip 3 → LIS(1,-∞)
 │   ├─ skip 1 → LIS(2,-∞)
 │   │   ├─ skip 2 → LIS(3,-∞)
 │   │   └─ take 2 → LIS(3,2)
 │   └─ take 1 → LIS(2,1)
 │       ├─ skip 2 → LIS(3,1)
 │       └─ take 2 → LIS(3,2)
 └─ take 3 → LIS(1,3)
     ├─ skip 1 → LIS(2,3)
     └─ take 1 (impossible because 1<3)

Example 5: Grid Path Sum

int n, m, s[10][10];

long long solve(int i, int j) {
    if (i == n || j == m) return -1e15;          // invalid
    if (i == n - 1 && j == m - 1) return s[i][j]; // base case

    long long ch1 = solve(i, j + 1);
    long long ch2 = solve(i + 1, j);

    return max(ch1, ch2) + s[i][j];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> s[i][j];

    cout << solve(0, 0);
}

Call tree for a small grid will branch right/down at each step.

Recap

• Recursion = function calling itself.
• Always have a base case to stop.
• Modify input each call to move closer to base case.
• Everything after the recursive call runs only when deeper calls finish.

Once you understand the push/pop stack model, recursion becomes natural and you can apply it to many CP problems.

The idea of two pointers is that instead of checking all possible pairs or subarrays with two nested loops (which might be O(n²)), you can often move two indices intelligently so that the total work becomes O(n + m).

This trick is common in merging arrays, counting pairs, or working with subarrays.

1. Merging Two Sorted Arrays in O(n + m)

Naive way: copy both arrays into a big array, then sort → O((n+m) log(n+m)).

But since they are already sorted, we can merge directly:

int n, m;
cin >> n >> m;
vector<int> f(n), s(m);
for (int i = 0; i < n; i++) cin >> f[i];
for (int i = 0; i < m; i++) cin >> s[i];

int l = 0, r = 0;
while (l < n && r < m) {
    if (f[l] < s[r]) {
        cout << f[l] << " ";
        l++;
    } else {
        cout << s[r] << " ";
        r++;
    }
}
while (l < n) cout << f[l++] << " ";
while (r < m) cout << s[r++] << " ";

2. Counting How Many Are Smaller

You have a sorted array f and many queries a in increasing order. For each query, print how many elements in f are < a.

int n, m; cin >> n >> m;
vector<int> f(n);
for (int i = 0; i < n; i++) cin >> f[i];

int j = 0;
for (int i = 0; i < m; i++) {
    int a; cin >> a;
    while (j < n && f[j] < a) j++;
    cout << j << " ";
}

Time: O(n + m).

Important: Just because you have a while inside a for does not mean O(n*m) automatically. If j only moves forward and never backtracks, the total work of the inner loop is O(n) over all iterations.

3. Counting Equal Pairs

Two sorted arrays a and b. Count the total pairs (i,j) such that a[i] == b[j].

Example:

a: 1 1 3 3 3 5 8 8
b: 1 3 3 4 5 5 5

We can do this in O(n + m):

int n, m; cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];

long long l = 0, r = 0, ans = 0;
for (int i = 0; i < n; i++) {
    while (l < m && b[l] < a[i]) l++;
    while (r < m && b[r] <= a[i]) r++;
    ans += r - l; // number of b's equal to a[i]
}
cout << ans << "\n";

4. Subarray Problems — Sliding Window Pattern

Two pointers become “left” and “right” indices of a window. We grow or shrink the window to maintain some property.

(a) Longest segment with sum ≤ s

int n, s; cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

long long l = 0, r = 0, ans = 0, sum = 0;
while (l < n) {
    while (r < n && sum + a[r] <= s) {
        sum += a[r];
        r++;
    }
    ans = max(ans, r - l);
    sum -= a[l];
    l++;
}
cout << ans;

(b) Smallest segment with sum ≥ s

int n, s; cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

long long l = 0, r = 0, ans = LLONG_MAX, sum = 0;
while (l < n) {
    while (r < n && sum < s) {
        sum += a[r];
        r++;
    }
    if (sum >= s) ans = min(ans, r - l);
    sum -= a[l];
    l++;
}
if (ans == LLONG_MAX) ans = -1;
cout << ans;

5. Generic Two-Pointer Template

Many problems follow the same skeleton:

long long l = 0, r = 0, ans = 0, sum = 0;
while (l < n) {
    while (r < n && can_add(r)) {
        add(r);
        r++;
    }
    ans = max(ans, r - l); // or min, or something else
    remove(l); // usually sum -= a[l];
    l++;
}
cout << ans;

6. Sliding Window with Fixed Size (Binary Search on Length)

Sometimes you are asked: What is the maximum size of a segment such that its sum ≤ s You can binary search on the length and check with a fixed-size window:

bool can(int len, const vector<int>& a, int s) {
    long long sum = 0;
    for (int i = 0; i < len; i++) sum += a[i];
    if (sum <= s) return true;
    for (int i = len; i < (int)a.size(); i++) {
        sum += a[i] - a[i - len];
        if (sum <= s) return true;
    }
    return false;
}

Then binary search on len:

int n, s; cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

int l = 0, r = n, ans = 0;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (can(mid, a, s)) {
        ans = mid;
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}
cout << ans;

Summary

• Two pointers turn many O(n²) problems into O(n) or O(n + m).
• The key is that both pointers only move forward.
• The pattern works for merging, counting, and sliding window problems.

Imagine you have a row of boxes. Each box has a number inside it. You don’t know the numbers, but you’re told the boxes are sorted in increasing order.

Now, you want to find whether a specific number x exists inside one of these boxes.

1. The Naive Way

Your first thought: “Let me open each box from left to right and check.”

That works, but in the worst case you’ll open all n boxes → O(n).

2. The Smarter Way

What if you could ignore half of the boxes at once?

How? By always checking the middle box:

• If a[mid] == x → found it.
• If a[mid] > x → you can safely ignore the right half (since everything there is larger).
• If a[mid] < x → ignore the left half.

Then, repeat the process on the remaining half.

This halves the range every step:

100 → 50 → 25 → 12 → 6 → 3 → 1

So in the worst case, you only open about log2(n) boxes.

That’s why binary search runs in O(log n).

3. Why Choose the Middle?

If you pick a random element (not the middle), you can’t guarantee you’ll eliminate a large part of the search space. The middle is optimal because it ensures we cut the range almost evenly each time.

4. Understanding Logarithm

log_x(y) = “How many times do I divide y by x until it becomes 1?”

For binary search, base = 2. So, log2(100) ≈ 7 → at most 7 steps to search among 100 elements.

5. C++ Implementation

// Standard Binary Search
int solve(vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int md = (l + r) / 2;
        if (a[md] == x) return md;     // found
        else if (a[md] < x) l = md + 1;
        else r = md - 1;
    }
    return -1; // not found
}

6. Binary Search on Answer (Important!)

Binary search isn’t only for searching in arrays. We often apply it when:

• We have many candidate answers.
• They follow a monotonic property (all bad → all good, or all good → all bad).

Examples:

1 1 1 1 1 0 0 0 → find the last "1"
0 0 0 0 0 1 1 1 → find the first "1"

We don’t search for a specific number, we search for the best candidate.

7. Upper Bound & Lower Bound

• lower_bound(a.begin(), a.end(), x) → first index with a[i] >= x.
• upper_bound(a.begin(), a.end(), x) → first index with a[i] > x.

Implementation of upper_bound:

int upper_bound(vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    int res = -1;
    while (l <= r) {
        int md = (l + r) / 2;
        if (a[md] > x) {
            res = md;      // candidate answer
            r = md - 1;    // try smaller index
        } else {
            l = md + 1;
        }
    }
    return res;
}

8. When to Use Binary Search?

Whenever:

• You want the smallest or largest element satisfying a condition.
• You have a monotonic function (true/false transition).

9. Practice Problems

• Packing Rectangles
• Closest to the Left

Key Takeaways

• Binary search = cut search space in half each step.
• Runs in O(log n).
• Works on sorted arrays or monotonic answers.
• Super useful for answer searching, not only for array elements.

If the array is sorted, use binary search → O(log n). If the array is not sorted, don’t sort it just to apply binary search → instead use linear search → O(n), which is more efficient.

Today we'll talk about Prefix Sums — one of the simplest and most powerful techniques in competitive programming.

Problem Motivation

Let's say I give you an array:

{5, 7, 1, 9, 1, 8}

and I ask you: "What's the sum of elements in a specific range [l..r]?"

Brute Force Solution

int n; cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];

int q; cin >> q;
while(q--){
    int l, r; cin >> l >> r;
    int ans = 0;
    for (int i = l; i <= r; i++){
        ans += v[i];
    }
    cout << ans << "\n";
}

Time complexity: O(n × q).

If n = 10⁶ and q = 10⁶ → O(10¹²) operations. Far too slow (will never finish in time).

We need something better. That's where Prefix Sum comes in.

Prefix Sum Idea

Instead of recomputing sums for every query, we preprocess:

p[i] = v[1] + v[2] + ... + v[i]

Each query can then be answered in O(1):

sum(l..r) = p[r] - p[l-1]

Why Does This Work?

Array:  [5, 7, 1, 9, 1, 8]
Prefix: [5, 12, 13, 22, 23, 31]

Query: sum from index 2 to 4
Answer = p[4] - p[1] = 22 - 5 = 17
Check:   7 + 1 + 9 = 17 ✓

Implementation

First Attempt (Buggy with 0-indexing)

int n; cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) cin >> v[i];

vector<int> p(n);
for(int i = 0; i < n; i++) p[i] = v[i] + p[i-1]; 
// Problem when i=0 → p[-1] (invalid!)

Correct Implementation (1-indexed arrays)

int n; cin >> n;
vector<int> v(n+1), p(n+1);
v[0] = p[0] = 0;

for(int i = 1; i <= n; i++) cin >> v[i];
for(int i = 1; i <= n; i++) p[i] = v[i] + p[i-1];

int q; cin >> q;
while(q--){
    int l, r; cin >> l >> r;
    cout << p[r] - p[l-1] << "\n";
}

Notice:

• Using 1-indexing avoids the negative index bug
• p[0] = 0 is a safe base case
• Time: O(n) preprocessing + O(1) per query

When to Use Prefix Sum?

Conditions:

1. Data must be static (no updates between queries)
2. The operation must have an inverse (like addition/subtraction)

Use cases:

• Range sum queries
• Range count queries
• Frequency queries in ranges
• 2D rectangle sum queries

Example 1: Count Ones in a Binary Array

Suppose you have an array of 0s and 1s, and you want to know how many ones are in range [l..r].

int n; cin >> n;
vector<int> v(n+1), p(n+1);
v[0] = p[0] = 0;

for(int i = 1; i <= n; i++) cin >> v[i];
for(int i = 1; i <= n; i++) p[i] = p[i-1] + v[i];

int q; cin >> q;
while(q--){
    int l, r; cin >> l >> r;
    int ones = p[r] - p[l-1];
    int zeros = (r - l + 1) - ones;
    cout << "Ones: " << ones << ", Zeros: " << zeros << "\n";
}

Key insight: Prefix sum works for counting, not just summing values.

Example 2: Count Letters in a String

Suppose I give you a string and queries like: "How many times does letter k appear in [l..r]?"

We can prepare 26 prefix arrays, one for each letter.

int n; cin >> n;
string s; cin >> s;
s = " " + s; // make it 1-indexed

vector<vector<int>> pref(26, vector<int>(n+1, 0));

// build prefix for each letter
for(int i = 0; i < 26; i++){
    for(int j = 1; j <= n; j++){
        int idx = s[j] - 'a';
        pref[i][j] = pref[i][j-1] + (i == idx);
    }
}

int q; cin >> q;
while(q--){
    int l, r; char c; cin >> l >> r >> c;
    int idx = c - 'a';
    cout << pref[idx][r] - pref[idx][l-1] << "\n";
}

Complexity:

• Preprocessing: O(26 × n)
• Query: O(1)

Example 3: 2D Prefix Sum (Sum in Rectangle)

Given a matrix, we want the sum of any sub-rectangle.

int n, m; cin >> n >> m;
vector<vector<int>> v(n+1, vector<int>(m+1, 0));

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        cin >> v[i][j];

// Build prefix sum
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
    }
}

int q; cin >> q;
while(q--){
    int xs, ys, xe, ye;
    cin >> xs >> ys >> xe >> ye;
    int ans = v[xe][ye] - v[xe][ys-1] - v[xs-1][ye] + v[xs-1][ys-1];
    cout << ans << "\n";
}

Visual Explanation

To get sum of rectangle (xs,ys) to (xe,ye):

ans = [full rectangle to (xe,ye)]
    - [rectangle to (xe, ys-1)]
    - [rectangle to (xs-1, ye)]
    + [rectangle to (xs-1, ys-1)]  // added back (was subtracted twice)

This technique is often called 2D Prefix Sum.

Example 4: Frequency Array

If we only need counts of numbers:

int n; cin >> n;
vector<int> v(n), freq(1e5+1, 0);

for(int i=0;i<n;i++) cin >> v[i], freq[v[i]]++;

int q; cin >> q;
while(q--){
    int x; cin >> x;
    cout << freq[x] << "\n";
}

Problem with Multiple Test Cases

Re-initializing freq every time = TLE.

Optimized Solution

vector<int> freq(1e5+1, 0);
int t; cin >> t;
while(t--){
    int n; cin >> n;
    vector<int> v(n);

    for(int i=0;i<n;i++){
        cin >> v[i];
        freq[v[i]] = 0; // reset only used values
    }

    for(int i=0;i<n;i++) freq[v[i]]++;

    int q; cin >> q;
    while(q--){
        int x; cin >> x;
        cout << freq[x] << "\n";
    }
}

Key optimization: Only reset values that were actually used, not the entire array.

Example 5: Range Updates (Difference Array)

Sometimes the problem is reversed: "You're given many operations: add a value v to all elements in range [l..r]. Output final array."

This is where difference array (also called partial sum) comes in:

int n, q; cin >> n >> q;
vector<int> diff(n+2, 0);

while(q--){
    int l, r, val; cin >> l >> r >> val;
    diff[l] += val;
    diff[r+1] -= val;
}

// build final array
vector<int> arr(n+1);
arr[1] = diff[1];
for(int i=2;i<=n;i++) arr[i] = arr[i-1] + diff[i];

for(int i=1;i<=n;i++) cout << arr[i] << " ";

How It Works

Operation: add 5 to range [2, 4]
diff[2] += 5   → effect starts at index 2
diff[5] -= 5   → effect ends after index 4

After all operations, build prefix sum of diff array
→ gives final array values

Use case: When you have many range updates but only need the final state.

Complexity Comparison

For n = 10⁶, q = 10⁶: - Brute Force: 10¹² operations (too slow) - Prefix Sum: 2×10⁶ operations (fast)

Practice Problems

Easy

• CSES — Static Range Sum Queries — Direct application of prefix sum
• CSES — Subarray Sums I — Prefix sum with target finding
• Codeforces 816B — Karen and Coffee — Range updates with difference array

Medium

• CSES — Subarray Divisibility — Prefix sum with modular arithmetic
• CSES — Forest Queries — 2D prefix sum application

Challenge Questions

1. Given an array, answer how many times a number x appears in range [l..r], where x is different for each query.

Hint: Build a 2D structure or use coordinate compression with prefix sums.

1. What if you are asked to add values to a range like: A[l] += v A[l+1] += 2*v A[l+2] += 3*v ... A[r] += (r-l+1)*v

Hint: Use difference array with arithmetic progression properties.

Summary

Prefix sums are an essential tool that will appear again in many problems: range queries, strings, matrices, frequency counting, range updates, and more.

Master this technique, and you'll solve a whole class of problems effortlessly.

Next topics to explore: - Sparse Table for range minimum queries - Segment Trees for dynamic range queries - Fenwick Trees (Binary Indexed Trees) for updates and queries

Questions? Drop them in the comments!

CSES 1084 – Apartments

We match applicants with apartments. Each applicant can take an apartment within ±k of his desired size.

// https://cses.fi/problemset/task/1084/
int n, m, k; 
cin >> n >> m >> k;

vector<int> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
sort(s.begin(), s.end());

multiset<int> ms;
while (m--) {
    int x; cin >> x;
    ms.insert(x);
}

int ans = 0;
for (int i = 0; i < n; i++) {
    int l = s[i] - k, r = s[i] + k;
    auto it = ms.lower_bound(l);   // first apt >= l
    if (it != ms.end() && *it <= r) {
        ans++;
        ms.erase(it); 
    }
}
cout << ans << "\n";

CSES 1091 – Concert Tickets

Each customer wants a ticket with price ≤ x.

// https://cses.fi/problemset/task/1091/
int n, m; 
cin >> n >> m;

multiset<int> ms;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    ms.insert(x);
}

for (int i = 0; i < m; i++) {
    int a; cin >> a;
    auto it = ms.upper_bound(a); // first element > a
    if (it != ms.begin()) {
        --it;                   
        cout << *it << "\n";
        ms.erase(it);
    } else {
        cout << -1 << "\n";
    }
}

Codeforces 637B – Chat Order

We need to print the chat names in the order of their last appearance.

// https://codeforces.me/problemset/problem/637/B
int n; cin >> n;
vector<string> x(n);
map<string, char> m;

for (int i = 0; i < n; i++) {
    cin >> x[i];
    m[x[i]] = 'n';
}

for (int i = n - 1; i >= 0; i--) {
    if (m[x[i]] == 'n') {
        cout << x[i] << "\n";
        m[x[i]] = 'y';
    }
}

These three problems cover:

• lower_bound and upper_bound on multisets
• Erasing elements safely
• Using map to track visits and preserve last appearance

Notes

1. Use vector<pair<int,int>> instead of map to keep all intervals (map removes duplicates and sorts only by key).
2. Sort intervals by end time using a lambda comparator:

cpp sort(v.begin(), v.end(), [](auto &x, auto &y){ return x.second < y.second; }); ---

Advanced STL Structures — A Complete Guide

Hi everyone! In this lecture we'll go deeper into STL structures that are must-know for competitive programming.

1. Iterators & Vectors

Iterators are like pointers that let you navigate through containers.

vector<int> v = {1, 2, 3, 4, 5};

auto it = v.begin();           // points to first element
auto end = v.end();            // points AFTER last element

sort(v.begin(), v.end());      // sort entire vector
v.end() - v.begin();           // size of vector

Key Facts

• v.begin() → iterator to first element
• v.end() → iterator AFTER last element (not the last element itself!)
• v.size() = v.end() - v.begin()

Important Trick

Count numbers in range [l, r] = r - l + 1.

This formula appears constantly in: - Binary search problems - Range queries - Coordinate compression

Example: cpp // How many integers from 5 to 10 inclusive? int count = 10 - 5 + 1; // = 6 (which is: 5,6,7,8,9,10)

2. lower_bound & upper_bound

Must use on a sorted container.

vector<int> v = {1, 3, 3, 5, 7, 9};

auto it1 = lower_bound(v.begin(), v.end(), 3);  // first element >= 3
auto it2 = upper_bound(v.begin(), v.end(), 3);  // first element > 3

Visual Example

Array: [1, 3, 3, 5, 7, 9]
              ↑     ↑
       lower_bound(3)  upper_bound(3)

Common Use Cases

Complete Example

vector<int> v = {1, 3, 3, 5, 7, 9};
sort(v.begin(), v.end());  // ensure sorted

// Count numbers in range [3, 7]
int count = upper_bound(v.begin(), v.end(), 7) - 
            lower_bound(v.begin(), v.end(), 3);
// Result: 4 (elements: 3, 3, 5, 7)

3. Binary Search Tree (BST) — Theory

Understanding BSTs helps you understand set and map internals.

Structure

• Each node has: parent, left child, right child
• BST Property: left < parent < right

        5
       / \
      3   8
     / \   \
    1   4   9

Why BST?

Balance Condition

A balanced BST maintains: |size(left) - size(right)| ≤ 1

C++ uses self-balancing BSTs (Red-Black Trees) to guarantee O(log n) operations.

4. set

Stores unique, sorted elements using a balanced BST.

set<int> st;
st.insert(6);
st.insert(3);
st.insert(5);
st.insert(1);
st.insert(3);  // duplicate ignored

for(auto x : st) 
    cout << x << " ";  // Output: 1 3 5 6

Key Operations

set<int> st = {1, 3, 5, 7, 9};

// Search
auto it = st.find(5);          // iterator to 5, or st.end() if not found
if(it != st.end()) {
    cout << "Found: " << *it;
}

// Insert
st.insert(4);                  // O(log n)

// Erase
st.erase(3);                   // erase by value
st.erase(st.find(5));          // erase by iterator

// Min/Max
int min_val = *st.begin();     // smallest element
int max_val = *st.rbegin();    // largest element
// Alternative: *(--st.end())

Important Limitations

No indexing — st[2] does NOT work

No random access — cannot jump to middle element directly

Common Pattern: Make Vector Distinct

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};

// Method 1: Using set
set<int> st(v.begin(), v.end());
v.assign(st.begin(), st.end());

// Method 2: sort + unique (faster)
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

5. multiset

Same as set, but allows duplicates.

multiset<int> ms = {1, 2, 3, 4, 4, 4, 5, 5};

ms.insert(4);     // now has 4 copies of 4
ms.erase(4);      // WARNING: erases ALL 4's!

// To erase only ONE occurrence:
ms.erase(ms.find(4));

Critical Difference

multiset<int> ms = {1, 2, 2, 2, 3};

ms.erase(2);              // removes ALL 2's → {1, 3}
ms.erase(ms.find(2));     // removes ONE 2 → {1, 2, 2, 3}

Count Occurrences

multiset<int> ms = {1, 2, 2, 2, 3};
int cnt = ms.count(2);    // O(log n + k), where k = count

Advanced Example: Find Second Greater Element

multiset<int> ms = {1, 3, 5, 7, 9};

int secondGreater(int x) {
    auto it = ms.upper_bound(x);    // first element > x
    if(it == ms.end()) return -1;   // no element > x
    
    it = ms.upper_bound(*it);       // second element > x
    if(it == ms.end()) return -1;   // only one element > x
    
    return *it;
}

// Example: secondGreater(3) → 7

6. map

Stores key → value pairs, sorted by key.

map<string, int> mp;

mp["apple"] = 5;
mp["banana"] = 10;
mp.insert({"cherry", 15});

for(auto [key, value] : mp) {
    cout << key << " → " << value << "\n";
}
// Output (sorted by key):
// apple → 5
// banana → 10
// cherry → 15

Key Operations

map<string, int> mp;

// Access (creates if doesn't exist)
mp["apple"] = 5;
cout << mp["banana"];       // 0 (default value)

// Check existence
if(mp.find("apple") != mp.end()) {
    cout << "Found";
}
// Or:
if(mp.count("apple")) {
    cout << "Found";
}

// Erase
mp.erase("apple");

// First and last elements
auto first = mp.begin();
cout << first->first << " → " << first->second;

auto last = mp.rbegin();  // reverse iterator
cout << last->first << " → " << last->second;

lower_bound and upper_bound on Maps

map<int, string> mp = {{1,"a"}, {5,"b"}, {9,"c"}};

auto it = mp.lower_bound(4);   // iterator to {5,"b"}
auto it2 = mp.upper_bound(5);  // iterator to {9,"c"}

Note: These work on keys, not values.

Default Values

map<int, int> freq;
freq[5]++;     // freq[5] starts at 0, becomes 1

map<int, vector<int>> adj;
adj[3].push_back(7);  // creates empty vector first

7. priority_queue

A heap that keeps elements sorted. Always access the largest (or smallest) element in O(1).

Max Heap (Default)

priority_queue<int> pq;  // max heap

pq.push(5);
pq.push(2);
pq.push(8);
pq.push(1);

cout << pq.top();  // 8
pq.pop();
cout << pq.top();  // 5

Min Heap

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(5);
pq.push(2);
pq.push(8);

cout << pq.top();  // 2

Custom Comparator

// Sort pairs by second element
priority_queue
    pair<int,int>, 
    vector<pair<int,int>>, 
    greater<pair<int,int>>
> pq;

pq.push({1, 10});
pq.push({2, 5});
pq.push({3, 15});

auto top = pq.top();  // {2, 5} (smallest second element)

When to Use

• Dijkstra's algorithm → min heap of distances
• Greedy problems → always process smallest/largest element
• Event simulation → process events in time order

Comparison Table

Common Patterns

Pattern 1: Frequency Map

map<int, int> freq;
for(int x : arr) 
    freq[x]++;

// Find most frequent
int max_freq = 0;
for(auto [val, cnt] : freq)
    max_freq = max(max_freq, cnt);

Pattern 2: Sliding Window with Set

// Find if any subarray of size k has all distinct elements
set<int> window;
for(int i = 0; i < n; i++) {
    window.insert(arr[i]);
    if(i >= k) window.erase(arr[i-k]);
    
    if(window.size() == k) {
        cout << "Found at " << i-k+1;
    }
}

Pattern 3: Lower Bound for Closest Element

set<int> st = {1, 5, 10, 15, 20};
int x = 12;

auto it = st.lower_bound(x);

int closest;
if(it == st.end()) {
    closest = *prev(it);  // all elements < x
} else if(it == st.begin()) {
    closest = *it;        // all elements >= x
} else {
    // Check both neighbors
    int right = *it;
    int left = *prev(it);
    closest = (x - left < right - x) ? left : right;
}

Practice Problems

Easy

• CSES — Apartments — Two pointers + sorting
• CSES — Concert Tickets — Multiset usage
• CSES — Sum of Two Values — Map or two pointers

Medium

• CSES — Movie Festival — Greedy + sorting
• CSES — Towers — Multiset + greedy
• CSES — Traffic Lights — Set + multiset combo

Summary

These STL tools are competitive programming superpowers.

Master them, and you'll solve problems faster and cleaner than ever before.

Next topics to explore: - Unordered containers (unordered_set, unordered_map) - Custom comparators for set and priority_queue - STL algorithms (next_permutation, accumulate, partial_sum)

Questions? Drop them in the comments!

Hi everyone!
Let's talk about some basic STL containers, their pros/cons, and when to use each.

Table of Contents

• Array
• Vector
• Deque
• Stack
• Queue
• TL;DR
• Tips & Tricks
• Practice Problems

1. Array

• Fixed size.
• Contiguous in memory → random access is O(1).
• Disadvantage: you can't add or erase elements.

int arr[5]; // size is fixed

2. Vector

• Dynamic array — like an array but resizable.
• Contiguous in memory (same as array).
• Adding/removing at the end is O(1).
• Insertion/erasure in the middle or front is O(n) — avoid when possible.

Common functions:

vector<int> v(n);        // size n, all zeros
vector<int> v;           // empty vector

v.push_back(10);          // add to end  — O(1)
v.pop_back();             // remove last — O(1)
v.resize(100);            // change size
if (v.empty()) ...        // check if empty

for (auto x : v) cout << x;   // range-based for loop

v.erase(v.begin());            // erase first element — O(n)
v.insert(v.begin(), 7);        // insert at front     — O(n)

3. Deque (Double Ended Queue)

• Solves vector's weakness at the front.
• Supports push_front() / pop_front() in O(1).
• Everything else works the same as vector.

deque<int> d;
d.push_back(5);
d.push_front(3);
d.pop_back();
d.pop_front();

4. Stack

• LIFO — Last In, First Out.
• You can only access the most recently pushed element.
• Classic use case: bracket checking.

stack<int> s;
s.push(10);
s.pop();
cout << s.top();
cout << s.size();
if (s.empty()) ...

5. Queue

• FIFO — First In, First Out.
• Access only the front and back elements.

queue<int> q;
q.push(5);         // enqueue
q.pop();           // dequeue (removes front)
cout << q.front();
cout << q.back();

TL;DR

• Array — fixed size, fastest random access.
• Vector — dynamic, fast at the back, slow at the front.
• Deque — dynamic, fast at both ends.
• Stack — LIFO.
• Queue — FIFO.

Tips & Tricks

Inserting at a specific index

v.insert(v.begin() + i, x);      // insert before index i
v.insert(v.begin() + i + 1, x);  // insert after index i

Finding the index of a value with std::find

auto it  = find(v.begin(), v.end(), x);
int  idx = it — v.begin();   // index of x in v

Sorting

sort(v.begin(), v.end());              // ascending
sort(v.rbegin(), v.rend());            // descending
sort(v.begin() + l, v.begin() + r);   // sort subarray [l, r)

Reversing

reverse(v.begin(), v.end());             // reverse entire vector
reverse(v.begin() + l, v.begin() + r);  // reverse subarray [l, r)

Lower Bound / Upper Bound

Important: the vector must be sorted first.

// first element >= x
auto it  = lower_bound(v.begin(), v.end(), x);
int  idx = it — v.begin();

// first element > x
auto it2  = upper_bound(v.begin(), v.end(), x);
int  idx2 = it2 — v.begin();

// count occurrences of x
int cnt = upper_bound(v.begin(), v.end(), x)
        — lower_bound(v.begin(), v.end(), x);

Quick rules:

• lower_bound(x) → index of first element ≥ x
• upper_bound(x) → index of first element > x
• Both are binary search → O(log n)

Practice Problems

AtCoder problems:

• ABC237 D — LR Insertion
• ABC158 D — String Formation
• ABC103 B — String Rotation
• ABC247 D — Cylinder
• ABC216 D — Pair of Balls

Codeforces problems (join the group first: STLs Contest Group):

Hi everyone This is Lecture 1 of the series. We’ll start with structs, how to use them, constructors, operator overloading, and finally pairs.

1. Motivation (Why Struct?)

We all know the basic data types:

int x;
string y;

But let’s say we have a company with 100 persons. Each person has:

• name (string)
• age (int)
• salary (float)

Naive approach:

string name[100];
int age[100];
float salary[100];

cin >> name[0] >> age[0] >> salary[0];

Problem: arrays are stored in different places in memory → not grouped.

Solution → Struct:

struct Person {
    string name;
    int age;
    float salary;
};

2. Using Struct

int main() {
    Person x;
    x.name = "Nourhan";
    x.age = 21;
    x.salary = 3000;

    cout << x.name << " " << x.age << " " << x.salary << endl;
}

Array of Persons:

Person p[5];
for (int i = 0; i < 5; i++) {
    cin >> p[i].name >> p[i].age >> p[i].salary;
}

• Just like int arr[5];
• p[i] = person i
• p[i].name = person i’s name

3. Declaration vs Initialization

int x;      // declaration
int y = 7;  // initialization

In structs we use constructor for initialization:

struct Person {
    string name;
    int age;
    float salary;

    Person(string a, int b, float c) {
        name = a;
        age = b;
        salary = c;
    }

    Person() {} // empty constructor
};

Usage:

int main() {
    Person p("Nourhan", 21, 4000);
    cout << p.name << " " << p.age << " " << p.salary;
}

4. Functions Inside vs Outside Struct

Inside:

struct Person {
    string name;
    int age;
    float salary;

    void read() {
        cin >> name >> age >> salary;
    }
};

Outside:

void read(Person &x) {
    cin >> x.name >> x.age >> x.salary;
}

Usage:

for (int i = 0; i < n; i++) {
    p[i].read();   // inside
    // read(p[i]); // outside
}

5. Operator Overloading

Problem: comparing two persons → which attribute?

struct Person {
    string name;
    int age;
    float salary;

    bool operator<(const Person &tmp) const {
        return salary < tmp.salary; // compare by salary
    }
};

Now we can:

sort(p, p + n); // uses operator<

For descending order:

return salary > tmp.salary;

6. Compare Function (Outside Struct)

bool compare(Person a, Person b) {
    return a.salary < b.salary;
}

sort(p, p + n, compare);

7. Pair

Like a mini-struct with just 2 elements.

pair<int,int> p;
cin >> p.first >> p.second;

Comparison: first → then second.

pair<int,int> p1 = {1,2};
pair<int,int> p2 = {1,5};

Custom compare:

bool comp(pair<int,int> &a, pair<int,int> &b) {
    if (a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

Summary

• Struct groups multiple variables in one type
• Can use arrays of structs
• Declaration vs initialization (constructors)
• Functions inside/outside struct
• Operator overloading (<)
• Compare functions
• Pair = built-in struct of 2 values