Core Problem-Solving Strategies

Bitwise Operations

Bitwise operators provide efficient alternatives to arithmetic operations:

Key optimizations:

• Use 1 << k instead of 2^k
• Use x >> k for integer division by 2^k (with parentheses)

Common bit manipulation patterns:

The lowbit function identifies the least significant set bit: lowbit(x) = x & -x.

Discretization

When dealing with large-value arrays where only relative ordering matters, discretization maps values to smaller integer ranges:

int size = originalArray.size();
vector<int> compressed;
for (int val : originalArray) {
    compressed.push_back(val);
}
sort(compressed.begin(), compressed.end());
compressed.erase(unique(compressed.begin(), compressed.end()), compressed.end());
for (int i = 0; i < size; i++) {
    originalArray[i] = lower_bound(compressed.begin(), compressed.end(), originalArray[i]) - compressed.begin();
}

Binary Lifting

Binary lifting decomposes operations into powers of two to achieve logarithmic complexity:

int steps = n;
int power = 1;
while (steps > 0) {
    if (steps >= power) {
        steps -= power;
        power *= 2;
    } else {
        power /= 2;
    }
}

Common used in LCA (Lowest Common Ancestor) algorithms.

Sparse Table for RMQ

Sparse Table precomputes range min/max queries in O(n log n) time with O(1) per query:

// Precomputation
vector<vector<int>> dp(n, vector<int>(LOG));
for (int i = 0; i < n; i++) {
    dp[i][0] = arr[i];
}
for (int j = 1; j < LOG; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
        dp[i][j] = min(dp[i][j-1], dp[i + (1 << (j-1))][j-1]);
    }
}

// Query [l, r]
int k = log2(r - l + 1);
int result = min(dp[l][k], dp[r - (1 << k) + 1][k]);

Prefix Sums and Differences

1D Prefix Sum: Enables O(1) range sum queries:

prefix[0] = 0;
for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i-1] + arr[i-1];
}
int range_sum = prefix[r] - prefix[l-1];

2D Prefix Sum: Extends to grid operations:

prefix[i][j] = grid[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
int rect_sum = prefix[rx][ry] - prefix[lx-1][ry] - prefix[rx][ly-1] + prefix[lx-1][ly-1];

Difference Array: Efficiently applies range updates:

diff[l] += val;
diff[r+1] -= val;
// Reconstruct original array
for (int i = 1; i <= n; i++) {
    arr[i] = arr[i-1] + diff[i];
}

Union-Find Data Structure

Manages disjoint sets with efficient union and find operations:

vector<int> parent;
vector<int> rank;

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

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void union_sets(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (rank[a] < rank[b]) swap(a, b);
    parent[b] = a;
    if (rank[a] == rank[b]) rank[a]++;
}

Search Optimization Techniques

DFS Improvements

Key pruning strategies:

• Order Optimization: Process most promising branches first
• Feasibility Pruning: Skip branches that can't reach solution
• Optimality Pruning: Terminate when current path exceeds best solution
• Iterative Deepening: Incrementally increase depth limit

bool dfs(int depth) {
    if (depth > max_depth) return false;
    // ... search logic ...
}

// Usage
int depth = 0;
while (!dfs(depth)) depth++;

BFS Enhancements

0-1 BFS: Uses deque for edge weights 0/1:

deque<int> dq;
dq.push_front(start);
dist[start] = 0;
while (!dq.empty()) {
    int u = dq.front(); dq.pop_front();
    for (auto &[v, w] : graph[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            if (w == 0) dq.push_front(v);
            else dq.push_back(v);
        }
    }
}

Bi-directional BFS: Searches from both start and goal simultaneously.

Dynamic Programming Foundations

Core Principles

DP requires three properties:

• Optimal Substructure: Optimal solution contains optimal sub-solutions
• No Aftereffect: State transitions don't depend on path history
• Overlapping Subproblems: Subproblems recur multiple times

Key Components

DP requires defining:

• State: Problem configuration (e.g., dp[i] = max value up to index i)
• Transition: How to compute new state from previous states
• Base Case: Initial conditions for DP table

Classic DP Examples

Longest Increasing Subsequence (LIS):

vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

Longest Common Subsequence (LCS):

vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (a[i-1] == b[j-1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

0-1 Knapsack (Space Optimized):

vector<int> dp(W+1, 0);
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}