The following represents commonly encountered algorithmic challlenges during competitive programming practice, documented for reference purposes.

Basic Algorithms

Binary Search and Extremal Optimization

Binary search can be applied beyond sorted arrays. When elements on one side of an array satisfy a condition while the other side doesn't, this creates a form of order suitable for binary search. This technique helps find the minimal value that satisfies a condition ("minimize maximum") or the maximal value that satisfies a condition ("maximize minimum").

For maximizing the minimum value:

int searchMaxMin(int left, int right) {
    while (left < right) {
        int middle = (left + right + 1) / 2;
        if (conditionSatisfied(middle)) {
            left = middle;
        } else {
            right = middle - 1;
        }
    }
    return left;
}

For minimizing the maximum value:

int searchMinMax(int left, int right) {
    while (left < right) {
        int middle = (left + right) / 2;
        if (conditionSatisfied(middle)) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    return left;
}

Monotonic Queue and Sliding Window

Monotonic queues maintain maximum/minimum values within a range [L, R], typically storing indices rather than values.

deque<int> monoQueue;
for (int position = windowStart; position <= arrayEnd; ++position) {
    int indexToInsert = position - windowSize;
    
    while (!monoQueue.empty() && values[monoQueue.back()] <= values[indexToInsert]) {
        monoQueue.pop_back();
    }
    monoQueue.push_back(indexToInsert);
    
    while (!monoQueue.empty() && monoQueue.front() + rightBound < position) {
        monoQueue.pop_front();
    }
    
    result[position] = values[monoQueue.front()] + additionalValue[position];
}

Monotonic Stack

Used to find the nearest element before/after each position that satisfies a comparison relationship.

stack<int> stk;
for (int i = arraySize; i > 0; --i) {
    while (!stk.empty() && arrayValues[stk.top()] <= arrayValues[i]) {
        stk.pop();
    }
    resultArray[i] = stk.empty() ? 0 : stk.top();
    stk.push(i);
}

2D Prefix Sum

Standard version:

for (int row = 1; row <= height; ++row) {
    for (int col = 1; col <= width; ++col) {
        prefix[row][col] = prefix[row-1][col] + prefix[row][col-1] - 
                          prefix[row-1][col-1] + matrix[row][col];
    }
}

XOR version:

for (int row = 1; row <= height; ++row) {
    for (int col = 1; col <= width; ++col) {
        prefix[row][col] = prefix[row-1][col] ^ prefix[row][col-1] ^ 
                          prefix[row-1][col-1] ^ matrix[row][col];
    }
}

Disjoint Set Union

struct UnionFind {
    vector<int> parent;
    
    UnionFind(int size) : parent(size) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int findRoot(int node) {
        return parent[node] == node ? node : parent[node] = findRoot(parent[node]);
    }
    
    void unite(int first, int second) {
        parent[findRoot(first)] = findRoot(second);
    }
};

Dynamic Programming

Number Triangle Model: Multi-path Scenarios

Use state f[step][pos1][pos2] to represent maximum sum when two paths move from (1,1),(1,1) to (row1,col1),(row2,col2).

for (int step = 1; step <= rows + cols; ++step) {
    for (int pos1 = 1; pos1 <= rows; ++pos1) {
        for (int pos2 = 1; pos2 <= rows; ++pos2) {
            int col1 = step - pos1, col2 = step - pos2;
            if (col1 < 1 || col1 > cols || col2 < 1 || col2 > cols) continue;
            
            int weight = (col1 == col2) ? grid[pos1][col1] : 
                        grid[pos1][col1] + grid[pos2][col2];
            
            int bestPrev = max({state[step-1][pos1][pos2], 
                               state[step-1][pos1-1][pos2],
                               state[step-1][pos1][pos2-1], 
                               state[step-1][pos1-1][pos2-1]});
            state[step][pos1][pos2] = bestPrev + weight;
        }
    }
}

Longest Increasing Subsequence

Let dp[i] represent the minimum ending element of all non-decreasing subsequences of length i.

fill(dp.begin(), dp.end(), INF);
int maxLength = 0;
for (int i = 0; i < n; ++i) {
    if (dp[maxLength] < sequence[i]) {
        dp[++maxLength] = sequence[i];
    } else {
        *lower_bound(dp.begin() + 1, dp.begin() + maxLength + 1, sequence[i]) = sequence[i];
    }
}

Longest Common Subsequence to LIS Conversion

Transform LCS problem into LIS by renumbering elements based on their positions in the first sequence.

unordered_map<int, int> mapping;
for (int i = 0; i < n; ++i) {
    int val; cin >> val;
    mapping[val] = i;
}

vector<int> transformed;
for (int i = 0; i < n; ++i) {
    int val; cin >> val;
    transformed.push_back(mapping[val]);
}

// Apply LIS on transformed array
int lisLength = 0;
fill(dp.begin(), dp.end(), INF);
for (int num : transformed) {
    int pos = lower_bound(dp.begin() + 1, dp.begin() + lisLength + 1, num) - dp.begin();
    lisLength = max(lisLength, pos);
    dp[pos] = num;
}

Bounded Knapsack Binary Optimization

Convert bounded knapsack to 0/1 knapsack by decomposing item counts into powers of 2.

vector<int> weights, values;
for (int i = 0; i < itemCount; ++i) {
    int count, cost, price; cin >> count >> cost >> price;
    int remaining = count;
    
    for (int power = 1; power <= remaining; power *= 2) {
        weights.push_back(cost * power);
        values.push_back(price * power);
        remaining -= power;
    }
    
    if (remaining > 0) {
        weights.push_back(cost * remaining);
        values.push_back(price * remaining);
    }
}

// Standard 0/1 knapsack
for (int item = 0; item < weights.size(); ++item) {
    for (int capacity = totalCapacity; capacity >= weights[item]; --capacity) {
        dp[capacity] = max(dp[capacity], dp[capacity - weights[item]] + values[item]);
    }
}

Interval Dynamic Programming

Characteristics: problems that can be divided into mergeable subproblems.

for (int length = 2; length <= n; ++length) {
    for (int start = 1; start <= n - length + 1; ++start) {
        int end = start + length - 1;
        for (int split = start; split < end; ++split) {
            intervalDp[start][end] = min(intervalDp[start][end], 
                                       intervalDp[start][split] + intervalDp[split+1][end] + 
                                       prefixSum[end] - prefixSum[start-1]);
        }
    }
}

Graph Theory

All-Pairs Shortest Path

Floyd-Warshall algorithm for graphs with any edge weights (no negative cycles).

for (int intermediate = 1; intermediate <= vertexCount; ++intermediate) {
    for (int source = 1; source <= vertexCount; ++source) {
        for (int destination = 1; destination <= vertexCount; ++destination) {
            distance[source][destination] = min(distance[source][destination],
                                             distance[source][intermediate] + 
                                             distance[intermediate][destination]);
        }
    }
}

Single-Source Shortest Path with Positive Weights

Dijkstra's algorithm with priority queue optimization.

struct Vertex {
    int node, distance;
    bool operator>(const Vertex& other) const {
        return distance > other.distance;
    }
};

priority_queue<Vertex, vector<Vertex>, greater<Vertex>> pq;
vector<int> distances(vertexCount + 1, INF);
vector<bool> visited(vertexCount + 1, false);

void dijkstra(int start) {
    distances[start] = 0;
    pq.push({start, 0});
    
    while (!pq.empty()) {
        int current = pq.top().node; pq.pop();
        if (visited[current]) continue;
        visited[current] = true;
        
        for (auto& edge : adjacencyList[current]) {
            int next = edge.first, weight = edge.second;
            if (distances[next] > distances[current] + weight) {
                distances[next] = distances[current] + weight;
                pq.push({next, distances[next]});
            }
        }
    }
}

SPFA and Negative Cycle Detection

vector<int> dist(vertexCount + 1, INF), edgeCount(vertexCount + 1, 0);
vector<bool> inQueue(vertexCount + 1, false);
queue<int> q;

bool spfa(int start) {
    dist[start] = 0;
    inQueue[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        inQueue[current] = false;
        
        for (auto& edge : adjacencyList[current]) {
            int next = edge.first, weight = edge.second;
            if (dist[next] > dist[current] + weight) {
                dist[next] = dist[current] + weight;
                edgeCount[next] = edgeCount[current] + 1;
                
                if (edgeCount[next] >= vertexCount) return false; // negative cycle
                
                if (!inQueue[next]) {
                    q.push(next);
                    inQueue[next] = true;
                }
            }
        }
    }
    return true;
}

Kruskal's Minimum Spanning Tree Algorithm

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

UnionFind uf(vertexCount);
sort(edges.begin(), edges.end());

int mstWeight = 0, edgeCount = 0;
for (auto& edge : edges) {
    if (uf.findRoot(edge.u) != uf.findRoot(edge.v)) {
        uf.unite(edge.u, edge.v);
        mstWeight += edge.weight;
        edgeCount++;
    }
}

Lowest Common Ancestor

Binary Lifting Approach

const int MAX_LEVEL = 20;
vector<int> depth(vertexCount + 1, INF);
vector<vector<int>> ancestors(vertexCount + 1, vector<int>(MAX_LEVEL));

void preprocess(int root) {
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        
        for (int child : tree[current]) {
            if (depth[child] > depth[current] + 1) {
                depth[child] = depth[current] + 1;
                ancestors[child][0] = current;
                
                for (int level = 1; level < MAX_LEVEL; ++level) {
                    ancestors[child][level] = ancestors[ancestors[child][level-1]][level-1];
                }
                q.push(child);
            }
        }
    }
}

int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    
    for (int level = MAX_LEVEL - 1; level >= 0; --level) {
        if (depth[ancestors[x][level]] >= depth[y]) {
            x = ancestors[x][level];
        }
    }
    
    if (x == y) return x;
    
    for (int level = MAX_LEVEL - 1; level >= 0; --level) {
        if (ancestors[x][level] != ancestors[y][level]) {
            x = ancestors[x][level];
            y = ancestors[y][level];
        }
    }
    
    return ancestors[x][0];
}

Segment Trees

Point Updates Without Lazy Propagation

struct SegmentNode {
    int left, right, maxValue;
};

struct SegmentTree {
    vector<SegmentNode> tree;
    
    void build(int node, int left, int right) {
        tree[node].left = left;
        tree[node].right = right;
        
        if (left == right) return;
        
        int mid = (left + right) / 2;
        build(node * 2, left, mid);
        build(node * 2 + 1, mid + 1, right);
        pushUp(node);
    }
    
    void pushUp(int node) {
        tree[node].maxValue = max(tree[node * 2].maxValue, tree[node * 2 + 1].maxValue);
    }
    
    void update(int node, int position, int value) {
        if (tree[node].left == position && tree[node].right == position) {
            tree[node].maxValue = value;
            return;
        }
        
        int mid = (tree[node].left + tree[node].right) / 2;
        if (position <= mid) {
            update(node * 2, position, value);
        } else {
            update(node * 2 + 1, position, value);
        }
        pushUp(node);
    }
    
    int query(int node, int left, int right) {
        if (tree[node].left >= left && tree[node].right <= right) {
            return tree[node].maxValue;
        }
        
        int mid = (tree[node].left + tree[node].right) / 2;
        int result = INT_MIN;
        
        if (left <= mid) result = max(result, query(node * 2, left, right));
        if (right > mid) result = max(result, query(node * 2 + 1, left, right));
        
        return result;
    }
};

Range Updates with Lazy Propagation

struct LazyNode {
    int left, right;
    long long sum, lazy;
};

void pushDown(int node) {
    if (tree[node].lazy != 0) {
        tree[node * 2].lazy += tree[node].lazy;
        tree[node * 2].sum += (tree[node * 2].right - tree[node * 2].left + 1) * tree[node].lazy;
        tree[node * 2 + 1].lazy += tree[node].lazy;
        tree[node * 2 + 1].sum += (tree[node * 2 + 1].right - tree[node * 2 + 1].left + 1) * tree[node].lazy;
        tree[node].lazy = 0;
    }
}

void updateRange(int node, int left, int right, long long delta) {
    if (tree[node].left >= left && tree[node].right <= right) {
        tree[node].lazy += delta;
        tree[node].sum += (tree[node].right - tree[node].left + 1) * delta;
        return;
    }
    
    pushDown(node);
    int mid = (tree[node].left + tree[node].right) / 2;
    
    if (left <= mid) updateRange(node * 2, left, right, delta);
    if (right > mid) updateRange(node * 2 + 1, left, right, delta);
    
    pushUp(node);
}

Number Theory

Sieve of Eratosthenes

vector<bool> isPrime(maxValue + 1, true);
vector<int> primes;

void sieve() {
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i <= maxValue; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        
        for (int prime : primes) {
            if (i * prime > maxValue) break;
            isPrime[i * prime] = false;
            if (i % prime == 0) break;
        }
    }
}

Fast Exponentiation

long long fastPower(long long base, long long exponent, long long modulus) {
    base %= modulus;
    long long result = 1;
    
    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    
    return result;
}

Nth Decimal Digit Calculation

To find the nth digit after the decimal point in a/b:

long long getNthDigit(long long numerator, long long denominator, long long position) {
    return (numerator * fastPower(10, position - 1, denominator) * 10) / denominator % 10;
}