Problem A: Interval Coverage with Exclusions Given a sequence of operations on an integer range [p, q] (initially [1, 10^9]), each operation falls into one of three types:

Type 1: increase the lower bound to max(current lower bound, k) Type 2: decrease the upper bound to min(current upper bound, k) Type 3: add value k to a list of excluded points

The task is to count how many integers remain in [p, q] after all operations but not present in the exclusion list. The solution maintains valid bounds and collects excluded values, then counts valid numbers in the final interval excluding those in the list. If the valid range becomes empty (q < p), the answer is zero.

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

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        long long low = 1, high = 1000000000;
        vector<long long> excluded;
        
        for (int i = 0; i < n; ++i) {
            int type;
            long long val;
            cin >> type >> val;
            if (type == 1) {
                low = max(low, val);
            } else if (type == 2) {
                high = min(high, val);
            } else {
                excluded.push_back(val);
            }
        }
        
        if (high < low) {
            cout << 0 << '\n';
            continue;
        }
        
        int count = 0;
        for (long long x : excluded) {
            if (x >= low && x <= high) {
                count++;
            }
        }
        cout << (high - low + 1 - count) << '\n';
    }
    return 0;
}

Problem B: Game of Array Manipulation with Removal and Sign Flips Two players alternate turns: Alice removes exactly k elements from the array, then Bob flips the sign of exactly x remaining elements to make the final array sum as small as possible. Alice wants to maximize the final sum. Find the optimal final sum. Key insight: After sorting the array in ascending order, optimal strategies involve Alice removing either some largest or smallest elements, and Bobflip either the smallest values (to minimize sum). Using prefix sums, we brute-force all possible numbers (i from 0 to k) of elements Alice could delete from the end, compute the resulting minimum achievable sum under Bob’s play, and select the maximum over all choices.

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

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n, k, x;
        cin >> n >> k >> x;
        vector<long long> arr(n);
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
        }
        sort(arr.begin(), arr.end());
        
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        
        long long best = -2'000'000'000;
        for (int removed = 0; removed <= k; ++removed) {
            int left = n - removed;
            if (left < x) continue;
            
            // Bob flips x smallest remaining elements
            long long flipSum = prefix[x] - prefix[0];
            long long remainingSum = prefix[left] - prefix[x];
            
            long long finalSum = remainingSum - flipSum;
            best = max(best, finalSum);
        }
        cout << best << '\n';
    }
    return 0;
}

Problem C: Segment-based Modular Alignment Given a sequence of length n, partition it into equal-length segments. Determine how many divisors k of n (where segment length = k) allow the array to be rearranged such that for any segment position j (0 ≤ j < k), all elements at positions ≡ j (mod k) are congruent modulo k. Necessary condition: For all valid indices i, |a[i] - a[i + k]| must be divisible by k. This means the GCD of all such differences across the array must be divisible by k. Thus, let D be the GCD of all |a[i + k] - a[i]| for i = 1 to n−k. If D ≠ 1, then k divides D ⇒ k satisfies the condition.

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

int greatestCommonDivisor(int a, int b) {
    return b == 0 ? a : greatestCommonDivisor(b, a % b);
}

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        vector<int> data(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> data[i];
        }
        
        int countValid = 0;
        for (int segLen = 1; segLen <= n; ++segLen) {
            if (n % segLen != 0) continue;
            
            int g = 0;
            for (int i = 1; i + segLen <= n; ++i) {
                g = greatestCommonDivisor(g, abs(data[i + segLen] - data[i]));
            }
            if (g > 1) {
                countValid++;
            }
        }
        cout << countValid << '\n';
    }
    return 0;
}