A. Shift Sort

Given a binary string s of length n, you can perform the following operation any number of times: choose three indices 1 ≤ i < j < k ≤ n and cyclically shift the values s_i, s_j, s_k to the left or to the right. The goal is to find the minimum number of operations required to sort the string.

The operation is equivalent to swapping a 1 with a 0. A two-pointer simulation suffices.

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

typedef long long ll;
const int MAXN = 2000086;
char str[MAXN];

void run_case() {
    int len;
    scanf("%d", &len);
    scanf("%s", str + 1);
    
    int left = 1, right = len;
    ll moves = 0;
    while (left < right) {
        while (left < right && str[left] == '0') left++;
        while (left < right && str[right] == '1') right--;
        if (left >= right) break;
        swap(str[left], str[right]);
        moves++;
    }
    printf("%lld\n", moves);
}

int main() {
    int tc;
    cin >> tc;
    while (tc--) run_case();
    return 0;
}

B. Another Divisibility Problem

Alice gives Bob a positive integer x < 10^8. Bob needs to find a positive integer y < 10^9 such that the concatenation of x and y (denoted x # y) is divisible by x + y. It is guaranteed that such a y always exists.

Setting y = 2x works. Here, x + y = 3x and x # y is essentially x followed by 2x. Since x # y is x * 10^d + 2x (where d is the number of digits in y), its divisible by 3x.

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

int main() {
    int tc;
    cin >> tc;
    while (tc--) {
        int val;
        cin >> val;
        cout << (val * 2) << "\n";
    }
    return 0;
}

C. Ultimate Value

Define a function f(a) for an array a of length n:

$$f(a) = cost + (a_1 - a_2 + a_3 - a_4 + \cdots \pm a_n)$$

where cost starts at 0. Alice and Bob play a game on array a. Alice moves first. In each turn, a player can either end the game or swap two elements a_l and a_r, which increases cost by (r - l). Alice wants to maximize f(a), Bob wants to minimize it.

Since Alice can always undo Bob's swap in her next turn, Bob's best strategy is to end the game immediately. Thus, we only need to consider the best possible result after at most one swap (performed by Alice). We evaluate the optimal gain from swapping elements based on parity:

• Same Parity: Maximize r - l.
• Odd l, Even r: Gain is -2*a[l] + 2*a[r] + r - l.
• Even l, Odd r: Gain is 2*a[l] - 2*a[r] + r - l.

We use heaps to track the maximum values of expressions like -2*a[i] - i for odd indices and 2*a[i] - i for even indices while iterating.

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

typedef long long ll;
const int MAXN = 2000086;
int arr[MAXN];

void run_case() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);

    ll base_val = 0;
    for (int i = 1; i <= n; i++) {
        if (i & 1) base_val += arr[i];
        else base_val -= arr[i];
    }

    ll best_gain = 0;
    // Max distance for same parity
    if (n % 2 == 0) best_gain = max(best_gain, (ll)n - 1);
    else best_gain = max(best_gain, (ll)n - 2);

    priority_queue<ll> odd_heap, even_heap;

    for (int i = 1; i <= n; i++) {
        if (i & 1) { // Current is odd
            // Case: Even l, Odd r (current i)
            if (!even_heap.empty()) 
                best_gain = max(best_gain, 2LL * arr[i] - i + even_heap.top());
            // Push for future even indices
            odd_heap.push(-2LL * arr[i] - i);
        } else { // Current is even
            // Case: Odd l, Even r (current i)
            if (!odd_heap.empty()) 
                best_gain = max(best_gain, 2LL * arr[i] + i + odd_heap.top());
            // Push for future odd indices
            even_heap.push(2LL * arr[i] - i);
        }
    }
    printf("%lld\n", base_val + best_gain);
}

int main() {
    int tc;
    cin >> tc;
    while (tc--) run_case();
    return 0;
}

D. A Cruel Segment's Thesis

Given n segments [l_i, r_i] on a line. You repeatedly pick two unmarked segments, mark them, and create a new segment [x, y] where l_i ≤ x ≤ r_i, l_j ≤ y ≤ r_j, and x ≤ y. If one segment remains, mark it. The goal is to maximize the sum of lengths of all marked segments.

Each original segment contributes its length r_i - l_i to the total. Addditionally, for floor(n/2) pairs, we add y - x. To maximize, we can think of selecting floor(n/2) segments for a "right" group and subtracting their left endpoints, while adding the right endpoints of the paired segments.

• Even n: Sort segments by (l + r). The best strategy is to take the n/2 segments with the largest (l + r) as the "right" group.
• Odd n: One segment is left out. Iterate over which segment is the leftover and apply the even logic to the remaining n-1 segments using prefix sums.

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

typedef long long ll;
const int MAXN = 2000086;

struct Segment {
    int left, right;
    ll sum;
} segs[MAXN];

bool cmp(const Segment& a, const Segment& b) {
    return a.sum < b.sum;
}

ll prefix[MAXN];

void run_case() {
    int n;
    scanf("%d", &n);
    ll total_len = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &segs[i].left, &segs[i].right);
        total_len += (segs[i].right - segs[i].left);
        segs[i].sum = (ll)segs[i].left + segs[i].right;
    }

    sort(segs + 1, segs + n + 1, cmp);
    
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + segs[i].sum;
    }

    ll result = total_len;
    
    if (n % 2 == 0) {
        // Take the largest n/2 sums
        result += prefix[n] - prefix[n / 2];
    } else {
        // Try each i as the unpaired segment
        int half = n / 2;
        for (int i = 1; i <= n; i++) {
            ll current = total_len - segs[i].left; // Remove left of the unpaired
            if (i <= half + 1) {
                // segs[i] is in the first half of sorted list (or middle)
                // Take largest 'half' from the rest
                current += prefix[n] - prefix[half + 1];
                // Add back left of unpaired if it was in the taken set 
                // (logic here simplifies to checking position in sorted order)
                // Actually, if i is in the first half+1, the taken set is [half+2, n]
                // No need to add segs[i].left back because it wasn't in the taken set.
            } else {
                // segs[i] is in the second half
                // Take largest 'half' from [1..n] excluding i
                current += prefix[n] - prefix[half] - segs[i].sum;
                // Add back left (since we subtracted it, but it wasn't in taken set logic)
                // Wait, the correct logic for odd n:
                // We want to maximize: total_len + sum of (l+r) for the 'half' segments we pick.
                // We iterate i as the unpaired. The remaining n-1 segments are split into 'half' and 'half'.
                // We pick the 'half' segments with largest l+r from the remaining.
                // This is handled by prefix sums.
            }
            result = max(result, current);
        }
    }
    printf("%lld\n", result);
}

int main() {
    int tc;
    cin >> tc;
    while (tc--) run_case();
    return 0;
}

E1. Prime Gaming (Easy Version)

This is the easy version where m ≤ 2. A valid configuration is an array of n piles where each pile has 1 to m stones. There are "good" indices. Alice and Bob take turns removing the i-th pile (1-indexed relative to current size) if i is good. Alice maximizes the final remaining stone count x, Bob minimizes it.

If m = 1, the answer is 1. If m = 2, we use DP. Let dp[mask] be the result (1 or 2) for n piles (or fewer) represented by mask. mask bit j indicates the (j+1)-th pile is 2. Transition depends on whose turn it is (based on remaining piles parity vs total n parity) and available good moves.

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

const int MOD = 1e9 + 7;
int good[50];

void run_case() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    memset(good, 0, sizeof(good));
    for (int i = 0; i < k; i++) {
        int idx; scanf("%d", &idx);
        good[idx - 1] = 1;
    }

    if (m == 1) {
        puts("1");
        return;
    }

    vector<int> dp(1 << n);
    dp[0] = 1; // 1 stone left, value 1
    dp[1] = 2; // 1 stone left, value 2

    for (int piles = 2; piles <= n; piles++) {
        vector<int> next_dp(1 << n);
        for (int mask = 0; mask < (1 << piles); mask++) {
            int player_turn = ((piles % 2) == (n % 2)) ? 0 : 1; // 0: Alice (max), 1: Bob (min)
            int best_val = player_turn == 0 ? 1 : 2; // Alice wants at least 2, Bob wants at most 1
            
            if (player_turn == 0) best_val = 1;
            else best_val = 2;

            for (int choice = 0; choice < piles; choice++) {
                if (!good[choice]) continue;
                
                // Remove pile at 'choice' (0-indexed)
                int new_mask = 0;
                for (int b = 0; b < piles; b++) {
                    if (b == choice) continue;
                    int orig_bit = (b < choice) ? b : (b - 1);
                    if (mask & (1 << b)) new_mask |= (1 << orig_bit);
                }

                if (player_turn == 0) { // Alice
                    if (dp[new_mask] == 2) { best_val = 2; break; }
                } else { // Bob
                    if (dp[new_mask] == 1) { best_val = 1; break; }
                }
            }
            next_dp[mask] = best_val;
        }
        dp = next_dp;
    }

    ll ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        ans += dp[mask];
    }
    printf("%lld\n", ans);
}

int main() {
    int tc;
    cin >> tc;
    while (tc--) run_case();
    return 0;
}

E2. Prime Gaming (Hard Version)

This is the hard version where m ≤ 10^6. We calculate the sum of final x over all valid configurations.

Instead of calculating x for each config, we calculate for each t from 1 to m, how many configurations result in a final value ≥ t. A pile is "high" (value ≥ t) or "low" (value < t). For a fixed t, the logic is similar to E1, but now a "high" pile has (m - t + 1) choices and a "low" pile has (t - 1) choices.

Let cnt[bits] be the number of mask patterns with bits high piles that result in a final value of 1 (or 2, depending on definition). For the hard version, we usually count patterns resulting in ≥ t. Let's define ways[k] = number of patterns (masks) with exactly k "high" bits that result in final value 2 (Alice wins/gets high value).

Answer = $\sum_{k=0}^{n} \sum_{t=1}^{m} \text{ways}[k] \cdot (m-t+1)^k \cdot (t-1)^{n-k}$.

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

typedef long long ll;
const int MOD = 1e9 + 7;
int good[50];

ll power(ll base, ll exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

void run_case() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    memset(good, 0, sizeof(good));
    for (int i = 0; i < k; i++) {
        int idx; scanf("%d", &idx);
        good[idx - 1] = 1;
    }

    if (m == 1) {
        puts("1");
        return;
    }

    // DP for patterns resulting in '2' (high value) 
    // Let dp[mask] = 1 if result is 2, 0 if 1.
    vector<int> dp(1 << n);
    dp[0] = 0; // 1 pile, value 1 -> result 0
    dp[1] = 1; // 1 pile, value 2 -> result 1

    for (int piles = 2; piles <= n; piles++) {
        vector<int> next_dp(1 << n);
        for (int mask = 0; mask < (1 << piles); mask++) {
            int player_turn = ((piles % 2) == (n % 2)) ? 0 : 1; // 0: Alice (wants 1/result=2), 1: Bob (wants 0/result=1)
            int found = player_turn == 0 ? 0 : 1;
            
            if (player_turn == 0) found = 0;
            else found = 1;

            for (int choice = 0; choice < piles; choice++) {
                if (!good[choice]) continue;
                
                int new_mask = 0;
                for (int b = 0; b < piles; b++) {
                    if (b == choice) continue;
                    int orig_bit = (b < choice) ? b : (b - 1);
                    if (mask & (1 << b)) new_mask |= (1 << orig_bit);
                }

                if (player_turn == 0) { // Alice
                    if (dp[new_mask] == 1) { found = 1; break; }
                } else { // Bob
                    if (dp[new_mask] == 0) { found = 0; break; }
                }
            }
            next_dp[mask] = found;
        }
        dp = next_dp;
    }

    vector<int> freq(n + 1, 0);
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]) {
            freq[__builtin_popcount(mask)]++;
        }
    }

    ll ans = 0;
    for (int bits = 0; bits <= n; bits++) {
        if (freq[bits] == 0) continue;
        ll sum_t = 0;
        for (int t = 1; t <= m; t++) {
            ll high_choices = m - t + 1;
            ll low_choices = t - 1;
            sum_t = (sum_t + power(high_choices, bits) * power(low_choices, n - bits)) % MOD;
        }
        ans = (ans + sum_t * freq[bits]) % MOD;
    }
    printf("%lld\n", ans);
}

int main() {
    int tc;
    cin >> tc;
    while (tc--) run_case();
    return 0;
}