Problem B: Summation Game

This problem involves a game between two players, Alice and Bob, operating on an array of integers. Alice aims to maximize the final sum of the array elements, while Bob aims to minimize it. Alice moves first by removing up to k elements from the array. Subsequently, Bob selects up to x elements from the remaining array and negates their values (multiplies by -1).

To determine the optimal outcome, we must analyze the greedy strategies for both players. Since Bob wants to minimize the sum, he will always choose the largest available numbers to negate. Conversely, Alice wants to prevent Bob from negating large positive numbers. Therefore, Alice's optimal strategy involves removing the largest elements from the sorted array. However, removing elements reduces the total count, and depending on the values (especially if negatives are involved), removing fewer then k elements might yield a better result.

The solution involves sorting the array in ascending order. We then iterate through all possible counts of elements Alice might remove, ranging from 0 to k. For each scenario, we calculate the sum of the remaining elements and subtract twice the sum of the largest x elements among those remaining (since negating a value v changes the total sum by -2v). Prefix sums are utilized to efficiently calculate subarray sums during this iteration.

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

using ll = long long;

void process_test_case() {
    int n, k_limit, x_limit;
    if (!(std::cin >> n >> k_limit >> x_limit)) return;

    std::vector<ll> values(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> values[i];
    }

    std::sort(values.begin(), values.end());

    std::vector<ll> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + values[i];
    }

    ll max_score = -2e18; // Initialize with a sufficiently small number

    // Iterate over the number of elements Alice removes (i)
    for (int i = 0; i <= k_limit; ++i) {
        int remaining_count = n - i;
        if (remaining_count < 0) break;

        // Sum of remaining elements after Alice removes i largest
        ll current_sum = prefix[remaining_count];

        // Bob negates the largest x elements among the remaining
        int bob_negates = std::min(x_limit, remaining_count);
        int start_index = remaining_count - bob_negates;
        
        // Sum of elements Bob will negate
        ll bob_sum = prefix[remaining_count] - prefix[start_index];

        // Final score calculation
        ll final_score = current_sum - 2 * bob_sum;
        max_score = std::max(max_score, final_score);
    }

    std::cout << max_score << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    if (std::cin >> t) {
        while (t--) {
            process_test_case();
        }
    }
    return 0;
}

Problem C: Partitioning the Array

The objective is to find the number of valid integers k such that the array can be partitioned into subarrays of length k, where all elements at the same relative position within these subarrays are congruent modulo some integer m (where m ≥ 2).

First, for a partition to be valid, k must be a divisor of the array length n. We can iterate through all divisors of n to check potential values for k.

For a fixed k>, the condition requires that for every index i, a[i] ≡ a[i + k] (mod m). By the properties of modular arithmetic, this is equivalent to saying that mmust divide the absolute difference|a[i] - a[i + k]|. Consequently, mmust be a common divisor of all such differences across the array. To satisfy the conditionm ≥ 2, the greatest common divisor (GCD) of all these differences must be greater than 1. If the GCD is greater than 1, then a valid mexists for that specifick.

The algorithm involves enumerating all divisors of n. For each divisor, we compute the GCD of the differences between elements separated by that divisor step. If the resulting GCD exceeds 1, we increment our count of valid partitions.

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

using ll = long long;

ll compute_gcd(ll a, ll b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

bool validate_step(const std::vector<ll>& arr, int step, int size) {
    if (step == size) return true;
    
    ll common_divisor = 0;
    for (int i = 0; i < size - step; ++i) {
        ll diff = std::abs(arr[i] - arr[i + step]);
        common_divisor = compute_gcd(common_divisor, diff);
        if (common_divisor == 1) {
            return false;
        }
    }
    return common_divisor > 1;
}

void process_test_case() {
    int n;
    if (!(std::cin >> n)) return;

    std::vector<ll> arr(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    int valid_count = 0;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            if (validate_step(arr, i, n)) {
                valid_count++;
            }
            if (i * i != n) {
                int other_divisor = n / i;
                if (validate_step(arr, other_divisor, n)) {
                    valid_count++;
                }
            }
        }
    }

    std::cout << valid_count << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    if (std::cin >> t) {
        while (t--) {
            process_test_case();
        }
    }
    return 0;
}