Problem A

Given a snacks to distribute equally among b people. Snacks cannot be divided. Find the minimum number of additional snacks that need to be purchased.

Solution

Each person requires ceil(a/b) snacks. Therefore, the total snacks needed is ceil(a/b) * b. The additional snacks required is ceil(a/b) * b - a.

int snacks, people;
std::cin >> snacks >> people;
int needed = ((snacks + people - 1) / people) * people;
std::cout << needed - snacks << std::endl;

Problem B

Given an integer n (1 ≤ n ≤ 20) and values a₀, a₁, ..., a_{n-1}. Also given a value mask. Starting with sum = 0, for each bit i in mask's binary representation that is 1, add a_i to sum.

Solution

This problem can be solved using bitwise operations. For each position from 0 to n-1, check if the corresponding bit in mask is set using (mask >> i) & 1.

int n, mask;
std::cin >> n >> mask;
std::vector<long long=""> values(n);
for (int i = 0; i < n; i++) std::cin >> values[i];

long long result = 0;
for (int i = 0; i < n; i++) {
    if (mask & (1 << i)) {
        result += values[i];
    }
}
std::cout << result << std::endl;
</long>

Note: In C++, shifting a signed integer beyond its bit width results in undefined behavior, so using unsigned integers is safer.

Problem C

Given n intervals [l_i, r_i], find the maximum number of intervals covering any point on the number line.

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ l_i, r_i ≤ 10⁶

Solution

The key observation is that the point with maximum coverage must be one of the interval endpoints. We can use the difference array technique to solve this efficiently.

Method 1: Direct difference array with fixed size

const int MAX = 1000005;
std::vector<int> diff(MAX);

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> left(n), right(n);
    for (int i = 0; i < n; i++) {
        std::cin >> left[i] >> right[i];
        diff[left[i]]++;
        diff[right[i] + 1]--;
    }
    
    int maximum = 0;
    for (int i = 0; i < MAX; i++) {
        if (i > 0) diff[i] += diff[i - 1];
        maximum = std::max(maximum, diff[i]);
    }
    std::cout << maximum << std::endl;
}
</int></int>

Method 2: Coordinate compression for better memory efficiency

The time complexity can be improved to O(n log n) using coordinate compression. Only the actual endpoints that appear are included in the compressed array.

int n;
std::cin >> n;
std::vector<int> left(n), right(n);
std::vector<int> points;

for (int i = 0; i < n; i++) {
    std::cin >> left[i] >> right[i];
    points.push_back(left[i]);
    points.push_back(right[i] + 1);
}

std::sort(points.begin(), points.end());
points.erase(std::unique(points.begin(), points.end()), points.end());
int m = points.size();

std::vector<int> diff(m + 2, 0);
for (int i = 0; i < n; i++) {
    int p1 = std::lower_bound(points.begin(), points.end(), left[i]) - points.begin();
    int p2 = std::lower_bound(points.begin(), points.end(), right[i] + 1) - points.begin();
    diff[p1]++;
    diff[p2]--;
}

int maximum = 0;
for (int i = 1; i < m; i++) {
    diff[i] += diff[i - 1];
    maximum = std::max(maximum, diff[i]);
}
std::cout << maximum << std::endl;
</int></int></int>

A common mistake is forgetting that position 0 is not included in the prefix sum but still needs to be checked for maximum coverage.

Problem D

Given an unweighted tree with N nodes. For each of Q independent queries, given two nodes x and y, consider adding an edge directly connecting these two nodes. The edge is guaranteed not to already exist. Find the number of edges in the cycle formed by adding this edge.

Constraints: 1 ≤ N, Q ≤ 10⁵

Solution

In a tree, the simple path between any two nodes is always the shortest path. When adding an edge between x and y, the cycle formed consists of:

• The new edge (1 edge)
• The existing path from x to y

The number of edges in the path from x to y equals depth[x] + depth[y] - 2 * LCA(x, y), where LCA is the Lowest Common Ancestor. Therefore, the cycle length is this path length plus one for the new edge.

Several methods exist to compute LCA:

• Binary lifting - Preprocess in O(N log N), answer queries in O(log N)
• Tarjan's offline LCA - Uses union-find with DFS
• Heavy-light decomposition - Also enables path queries
• Euler tour + RMQ - O(N log N) preprocessing, O(1) per query with sparse table

All approaches have similar time complexity. Heavy-light decomposition tends to be faster in practice for random data, and it can handle more complex path operations.

// Binary lifting approach (conceptual)
int n, q;
std::cin >> n >> q;
std::vector<:vector>> tree(n + 1);

// Build tree, compute parent and depth via DFS
// Binary lift table: up[k][v] = 2^k-th ancestor of v
std::vector<:vector>> up(LOG, std::vector<int>(n + 1));
std::vector<int> depth(n + 1);

void dfs(int v, int p) {
    up[0][v] = p;
    for (int k = 1; k < LOG; k++) {
        up[k][v] = up[k-1][up[k-1][v]];
    }
    for (int to : tree[v]) {
        if (to != p) {
            depth[to] = depth[v] + 1;
            dfs(to, v);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) std::swap(a, b);
    int diff = depth[a] - depth[b];
    for (int k = 0; k < LOG; k++) {
        if (diff & (1 << k)) a = up[k][a];
    }
    if (a == b) return a;
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[k][a] != up[k][b]) {
            a = up[k][a];
            b = up[k][b];
        }
    }
    return up[0][a];
}

int path_length(int a, int b) {
    int ancestor = lca(a, b);
    return depth[a] + depth[b] - 2 * depth[ancestor];
}

while (q--) {
    int x, y;
    std::cin >> x >> y;
    int cycle = path_length(x, y) + 1;
    std::cout << cycle << std::endl;
}
</int></int></:vector></:vector>

While there exist more advanced techniques like O(1) LCA using RMQ on Euler tour with Cartesian trees, these optimizations are typically unnecessary for competitive programming. Understanding the fundamental algorithms and practicing problem-solving is more valuable than optimizing for minimal constant factors.