Problem A: Symmetric Pair Removal

Given a binary string of length n, repeatedly remove a pair of characters from opposite ends if they differ (one is '0' and the other is '1'). Calculate the remaining length after no more valid pairs can be removed.

A two-pointer technique efficiently solves this problem. Initialize pointers at the start and end of the string. While the left pointer is less than the right pointer and the characters differ, advance both pointers inward. The remaining length is simply the distance between the pointers plus one.

#include <iostream>
#include <string>

void solve() {
    int n;
    std::cin >> n;
    std::string binary_string;
    std::cin >> binary_string;
    
    int left = 0;
    int right = n - 1;
    
    while (left < right && binary_string[left] != binary_string[right]) {
        ++left;
        --right;
    }
    
    std::cout << (right - left + 1) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int test_cases;
    std::cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}

Problem B: Distinct Split Optimization

For a given string, split it at every possible position into a prefix and a suffix. Maximize the sum of distinct characters present in both parts.

Maintain frequency arrays for both the prefix and suffix. Initially, populate the suffix frequencies. Iterate through the string character by character, moving the current character from the suffix frequency array to the prefix array. At each step, count the number of non-zero entries in both arrays and update the maximum sum.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int countDistinct(const std::vector<int>& freq) {
    int distinct = 0;
    for (int count : freq) {
        if (count > 0) ++distinct;
    }
    return distinct;
}

void solve() {
    int n;
    std::cin >> n;
    std::string text;
    std::cin >> text;
    
    std::vector<int> prefixFreq(26, 0);
    std::vector<int> suffixFreq(26, 0);
    
    for (char c : text) {
        suffixFreq[c - 'a']++;
    }
    
    int maxScore = 0;
    for (char c : text) {
        int idx = c - 'a';
        suffixFreq[idx]--;
        prefixFreq[idx]++;
        maxScore = std::max(maxScore, countDistinct(prefixFreq) + countDistinct(suffixFreq));
    }
    
    std::cout << maxScore << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Problem C: Adjacent Sign Inversion

Given an integer array, you may repeatedly select two adjacent elements and negate both. Maximize the total sum of the array after any number of operations.

Negating two adjacent elements preserves the parity of negative numbers in the array. Sorting the array allows us to pair the smallest elements. If the sum of a pair is negative, negating them increases the total sum. Iterate through the sorted array in steps of two, applying the inversion whenever the pair sum is negative.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> nums(n);
    long long totalSum = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
        totalSum += nums[i];
    }
    
    std::sort(nums.begin(), nums.end());
    
    for (int i = 0; i + 1 < n; i += 2) {
        if (nums[i] + nums[i + 1] < 0) {
            totalSum -= 2 * (nums[i] + nums[i + 1]);
        }
    }
    
    std::cout << totalSum << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int testCases;
    std::cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}

Problem D: Range Update with Point Digit-Sum Query

Maintain an array supporting two operations: increment an operation counter for a range, and query a specific index by applying the digit-sum transformation a number of times equal to its counter. The digit-sum of a number ≤ 10⁹ rapidly converges to a single digit.

Use a Binary Indexed Tree (Fenwick Tree) to handle range updates and point queries efficiently. Each index stores how many times the digit-sum operation should be applied. During a query, retrieve the counter value and repeatedly apply the digit-sum transformation, breaking early once the value drops below 10.

#include <iostream>
#include <vector>

class FenwickTree {
    std::vector<int> tree;
    int size;
public:
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    
    void increment(int idx, int delta) {
        for (; idx <= size; idx += idx & -idx) {
            tree[idx] += delta;
        }
    }
    
    void rangeUpdate(int l, int r, int val) {
        increment(l, val);
        increment(r + 1, -val);
    }
    
    int query(int idx) const {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
};

int digitSum(int val) {
    int res = 0;
    while (val > 0) {
        res += val % 10;
        val /= 10;
    }
    return res;
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> original(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> original[i];
    }
    
    FenwickTree bit(n);
    
    for (int k = 0; k < q; ++k) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int l, r;
            std::cin >> l >> r;
            bit.rangeUpdate(l, r, 1);
        } else {
            int pos;
            std::cin >> pos;
            int ops = bit.query(pos);
            int val = original[pos];
            if (val >= 10) {
                while (ops-- > 0 && val >= 10) {
                    val = digitSum(val);
                }
            }
            std::cout ><< val << '\n';
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Problem E: Guard Pair Validation

Given a target sum n and four pairs of constraints, determine if any pair can form x + y = n such that x ≥ min(a, b) and y ≥ min(c, d). Output the first valid configuration or indicate failure.

For each of the four sets, compute the minimum required values for x and y. If the sum of these minimums does not exceed n, the condition is satisfied. Assign x to its minimum value and y to the remainder, then terminate.

#include <iostream>
#include <algorithm>

void solve() {
    long long target;
    std::cin >> target;
    
    for (int i = 1; i <= 4; ++i) {
        long long a, b, c, d;
        std::cin >> a >> b >> c >> d;
        
        long long minX = std::min(a, b);
        long long minY = std::min(c, d);
        
        if (minX + minY <= target) {
            std::cout << i << ' ' << minX << ' ' << (target - minX) << '\n';
            return;
        }
    }
    
    std::cout << -1 << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

Problem F: Stride Task Selection

Select tasks from an array by starting at an index and skipping k positions each time until n/k tasks are completed. Find the starting index (1 to k) that minimizes the total energy cost.

Iterate through all possible starting positions from 1 to k. For each start, accumulate the costs by stepping forward with a stride of k. Track the minimum accumulated cost and the corresponding starting index.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

void solve() {
    int n, k;
    std::cin >> n >> k;
    
    std::vector<long long> costs(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> costs[i];
    }
    
    long long minEnergy = LLONG_MAX;
    int bestStart = 1;
    
    for (int start = 1; start <= k; ++start) {
        long long currentEnergy = 0;
        for (int idx = start; idx <= n; idx += k) {
            currentEnergy += costs[idx];
        }
        
        if (currentEnergy < minEnergy) {
            minEnergy = currentEnergy;
            bestStart = start;
        }
    }
    
    std::cout << bestStart << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

Problem G: Balanced Knapsack Selection

Choose a subset of items to maximize the sum of values a[i] subject to the constraint that the sum of a[i] equals k times the sum of b[i]. This transforms in to finding a subset where the sum of (a[i] - k*b[i]) equals zero.

Use dynamic programming with an offset to handle negative weights. Define dp[offset + weight] as the maximum value achievable for a given net weight. Initialize the offset position to zero and others to negative infinity. Iterate through items, updating the DP table based on the transformed weight c[i] = a[i] - k*b[i]. The answer resides at the offset position after processing all items.

#include <iiostream>
#include <vector>
#include <algorithm>
#include <climits>

const int OFFSET = 100000;
const long long NEG_INF = -1e18;

void solve() {
    int n, k;
    std::cin >> n >> k;
    
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < n; ++i) std::cin >> b[i];
    
    std::vector<long long> dp(2 * OFFSET + 1, NEG_INF);
    dp[OFFSET] = 0;
    
    for (int i = 0; i < n; ++i) {
        int weight = a[i] - k * b[i];
        int value = a[i];
        
        if (weight >= 0) {
            for (int w = 2 * OFFSET; w >= weight; --w) {
                if (dp[w - weight] != NEG_INF) {
                    dp[w] = std::max(dp[w], dp[w - weight] + value);
                }
            }
        } else {
            for (int w = 0; w <= 2 * OFFSET + weight; ++w) {
                if (dp[w - weight] != NEG_INF) {
                    dp[w] = std::max(dp[w], dp[w - weight] + value);
                }
            }
        }
    }
    
    if (dp[OFFSET] == 0) {
        std::cout << -1 << '\n';
    } else {
        std::cout << dp[OFFSET] << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

Problem H: Maximum Path Interval Width

Find a path from vertex 1 to vertex n in an undirected graph where each edge has an allowed range [l, r]. Maximize the width (max_r - min_l + 1) among all edge on the chosen path.

Sort edges by their lower bound l. Iterate through each edge, treating its r value as a fixed right bound R. For each R, activate all edges where l ≤ R and r ≥ R. Use a Disjoint Set Union (DSU) structure to maintain connectivity. If vertices 1 and n become cnonected, update the answer with the maximum valid interval width.

#include <iiostream>
#include <vector>
#include <algorithm>
#include <iostream>

struct Edge {
    int u, v;
    int lower, upper;
};

struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx != ry) parent[rx] = ry;
    }
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].lower >> edges[i].upper;
    }
    
    std::sort(edges.begin(), edges.end(), [](const Edge& x, const Edge& y) {
        return x.lower < y.lower;
    });
    
    int maxInterval = 0;
    
    for (int i = 0; i < m; ++i) {
        DSU dsu(n);
        for (int j = 0; j < m; ++j) {
            if (edges[j].lower <= edges[i].upper && edges[j].upper >= edges[i].upper) {
                dsu.unite(edges[j].u, edges[j].v);
            }
        }
        
        if (dsu.find(1) == dsu.find(n)) {
            for (int j = 0; j < m; ++j) {
                if (edges[j].lower <= edges[i].upper && edges[j].upper >= edges[i].upper) {
                    maxInterval = std::max(maxInterval, edges[i].upper - edges[j].lower + 1);
                }
            }
        }
    }
    
    if (maxInterval == 0) {
        std::cout << "Nice work, Dima!" << '\n';
    } else {
        std::cout << maxInterval << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}