Problem A

Given a string, replace all 'A's with 'BB's, then greedily revert overlapping or consecutive 'BB's back to 'A's to minimize length. A direct greedy approach tracks a pending 'B' flag to handle conversions efficiently.

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int len;
    cin >> len;
    string str;
    cin >> str;
    bool has_pending_B = false;
    for (char ch : str) {
        if (ch == 'B') {
            if (has_pending_B) {
                cout << 'A';
                has_pending_B = false;
            } else {
                has_pending_B = true;
            }
        } else if (ch == 'A') {
            cout << 'A';
        } else {
            if (has_pending_B) {
                cout << 'B';
                has_pending_B = false;
            }
            cout << ch;
        }
    }
    if (has_pending_B) {
        cout << 'B';
    }
    cout << endl;
    return 0;
}

Problem B

Determine if two arrays of integers can be transformed into each other using a specific swap operation. The operation preserves inversion count parity, which is sufficient for permutations. For arrays with duplicates, ensure count of each number matches, then check for duplicates (which automatically allow transformation) or inversion count parity.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_VAL = 5000;

int read() {
    char c;
    int x = 0;
    while ((c = getchar()) < '0' || c > '9');
    do x = x * 10 + (c - '0');
    while ((c = getchar()) >= '0' && c <= '9');
    return x;
}

long long count_inversions(vector<int>& arr) {
    vector<int> bit(MAX_VAL + 2, 0);
    long long res = 0;
    for (int i = arr.size() - 1; i >= 0; --i) {
        int x = arr[i];
        int sum = 0;
        for (int j = x - 1; j > 0; j -= j & -j) {
            sum += bit[j];
        }
        res += sum;
        for (int j = x; j <= MAX_VAL; j += j & -j) {
            bit[j]++;
        }
    }
    return res;
}

int main() {
    int n = read();
    vector<int> cnt_a(MAX_VAL + 2, 0), cnt_b(MAX_VAL + 2, 0);
    vector<int> arr_a(n), arr_b(n);
    for (int i = 0; i < n; ++i) {
        arr_a[i] = read();
        cnt_a[arr_a[i]]++;
    }
    for (int i = 0; i < n; ++i) {
        arr_b[i] = read();
        cnt_b[arr_b[i]]++;
    }
    bool has_duplicates = false;
    for (int i = 1; i <= MAX_VAL; ++i) {
        if (cnt_a[i] != cnt_b[i]) {
            cout << "No" << endl;
            return 0;
        }
        if (cnt_a[i] > 1) {
            has_duplicates = true;
        }
    }
    if (has_duplicates) {
        cout << "Yes" << endl;
        return 0;
    }
    long long inv_a = count_inversions(arr_a);
    long long inv_b = count_inversions(arr_b);
    if ((inv_a % 2) == (inv_b % 2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Problem C

A circular array problem where operations split into intervals and merge adjacent ones. Breaking the circle at the minimum value position converts it to a linear problem. Use range minimum queries (RMQ) to recursively solve subarrays, accounting for possible interval merges based on min values.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int read() {
    char c;
    int x = 0;
    while ((c = getchar()) < '0' || c > '9');
    do x = x * 10 + (c - '0');
    while ((c = getchar()) >= '0' && c <= '9');
    return x;
}

typedef long long ll;
const int MAXN = 4e5 + 10;
const int LOG = 20;

int n;
vector<int> arr;
vector<int> lg_table;
vector<vector<int>> st;

int get_min_idx(int l, int r) {
    int len = r - l + 1;
    int k = lg_table[len];
    int a = st[k][l], b = st[k][r - (1 << k) + 1];
    return arr[a] < arr[b] ? a : b;
}

ll solve(int l, int r, ll current_level) {
    if (l > r) return 0;
    int min_pos = get_min_idx(l, r);
    ll left = solve(l, min_pos - 1, arr[min_pos]);
    ll right = solve(min_pos + 1, r, arr[min_pos]);
    ll merge = min({left, right, (ll)arr[min_pos]});
    return left + right + arr[min_pos] - current_level - merge;
}

int main() {
    n = read();
    arr.resize(n * 2);
    int min_val = INT_MAX;
    for (int i = 0; i < n; ++i) {
        arr[i] = read();
        min_val = min(min_val, arr[i]);
        arr[i + n] = arr[i];
    }
    lg_table.resize(n * 2 + 1);
    lg_table[1] = 0;
    for (int i = 2; i <= n * 2; ++i) {
        lg_table[i] = lg_table[i / 2] + 1;
    }
    st.resize(LOG + 1, vector<int>(n * 2));
    for (int i = 0; i < n * 2; ++i) {
        st[0][i] = i;
    }
    for (int k = 1; k <= LOG; ++k) {
        for (int i = 0; i + (1 << k) <= n * 2; ++i) {
            int a = st[k - 1][i];
            int b = st[k - 1][i + (1 << (k - 1))];
            st[k][i] = arr[a] < arr[b] ? a : b;
        }
    }
    int start = 0;
    while (arr[start] != min_val) {
        start++;
    }
    int end = start + n - 1;
    cout << solve(start, end, 0) << endl;
    return 0;
}

Problem D

Count pairs of numbers that add without carry in decimal. This is a classic high-dimensional prefix sum problem over digits. After computing the prefix sum, adjust for edge cases like numbers with digits greater than 4 (which cause carry with some pairs).

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1e6;
int count[MAX];

int read() {
    char c;
    int x = 0;
    while ((c = getchar()) < '0' || c > '9');
    do x = x * 10 + (c - '0');
    while ((c = getchar()) >= '0' && c <= '9');
    return x;
}

int main() {
    int n = read();
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        nums[i] = read();
        count[nums[i]]++;
    }
    for (int d = 0; d < 6; ++d) {
        int base = 1;
        for (int i = 0; i < d; ++i) {
            base *= 10;
        }
        for (int i = 0; i < MAX; ++i) {
            if ((i / base) % 10 > 0) {
                count[i] += count[i - base];
            }
        }
    }
    long long total = 0;
    for (int num : nums) {
        int target = 999999 - num;
        total += count[target];
        int temp = num;
        bool invalid = false;
        while (temp > 0) {
            if (temp % 10 > 4) {
                invalid = true;
                break;
            }
            temp /= 10;
        }
        if (invalid) {
            total++;
        }
        total--;
    }
    cout << total / 2 << endl;
    return 0;
}

Problem E

Maximize the sum of a connected subarray where every element is reachable from the others. Even numbers are all connected. For odd numbers, their minimal prime factors connect them to even neighbors. Use a difference array to track interval coverage of reachable regions from each odd number.

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 10;
int min_prime[MAXN];
int primes[MAXN / 10];
int prime_count;

void sieve(int limit) {
    for (int i = 2; i <= limit; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes[prime_count++] = i;
        }
        for (int j = 0; j < prime_count && primes[j] <= min_prime[i] && primes[j] * i <= limit; ++j) {
            min_prime[primes[j] * i] = primes[j];
        }
    }
}

int read() {
    char c;
    int x = 0;
    while ((c = getchar()) < '0' || c > '9');
    do x = x * 10 + (c - '0');
    while ((c = getchar()) >= '0' && c <= '9');
    return x;
}

int main() {
    int n = read();
    vector<int> arr(n + 2);
    for (int i = 1; i <= n; ++i) {
        arr[i] = read();
    }
    sieve(n);
    vector<long long> diff(n * 2 + 4, 0);
    long long max_sum = arr[1];
    diff[1] += arr[1];
    diff[2] -= arr[1];
    for (int i = 2; i <= n; ++i) {
        if (i % 2 == 0) {
            diff[i] += arr[i];
            diff[i + 1] -= arr[i];
        } else {
            int l = i - min_prime[i] + 1;
            int r = i + min_prime[i];
            diff[l] += arr[i];
            diff[r] -= arr[i];
        }
    }
    long long current = 0;
    for (int i = 1; i <= n * 2; ++i) {
        current += diff[i];
        if (current > max_sum) {
            max_sum = current;
        }
    }
    cout << max_sum << endl;
    return 0;
}