String Character Annihilation

When two distinct characters in a string annihilate each other, the specific identity of the characters is irrelevant. As long as multiple distinct characters exist, they can be paired off. The goal of minimizing the remaining characters can be modeled as a two-pile stacking problem where items at the same height must differ. The minimal remaining length is determined by the maximum frequency of any character.

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

void process_case() {
    int length;
    string str;
    cin >> length >> str;
    vector<int> freq(26, 0);
    int max_freq = 0;
    for (char c : str) {
        freq[c - 'a']++;
        max_freq = max(max_freq, freq[c - 'a']);
    }
    cout << max(2 * max_freq - length, length % 2) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process_case();
    return 0;
}

Digit Partitioning without Carry

When determining the number of ways to sum three numbers to a target without any carry-over, bitwise analysis is applicable. It can be rigorously proven that no carry will occur across digits. Thus, the total combinations are the product of the combinations for each individual digit. For a digit `d`, the number of non-negative integer solutions to `x + y + z = d` is calculated by iterating through possible values of `x` and `y`.

#include <iostream>
using namespace std;
using ll = long long;

void process_case() {
    int num;
    cin >> num;
    ll total = 1;
    while (num > 0) {
        int digit = num % 10;
        num /= 10;
        int ways = 0;
        for (int x = 0; x <= digit; ++x) {
            for (int y = 0; y <= digit; ++y) {
                if (digit - x - y >= 0) ways++;
            }
        }
        total *= ways;
    }
    cout << total << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process_case();
    return 0;
}

Circular Array Monotonicity via Reverse and Shift

A sequence can be reversed entirely or shifted by moving the last element to the front. Since a shift alters the endpoint of the sequence in a circular array, we can enumerate all possible endpoints. For each endpoint, we check if the resulting array is entirely non-decreasing or non-increasing. If a valid monotonic sequence is found, the required operations are computed by considering the shift distance and the optional reverse operation. Different cases must be evaluated based on whether a reverse is applied.

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

void process_case() {
    int n;
    cin >> n;
    vector<int> arr(2 * n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        arr[i + n] = arr[i];
    }
    vector<int> inc(2 * n, 1), dec(2 * n, 1);
    for (int i = 1; i < 2 * n; ++i) {
        if (arr[i] >= arr[i - 1]) inc[i] = min(inc[i - 1] + 1, n);
        if (arr[i] <= arr[i - 1]) dec[i] = min(dec[i - 1] + 1, n);
    }
    int min_ops = 1e9;
    if (inc[n - 1] == n) min_ops = 0;
    else if (dec[n - 1] == n) min_ops = 1;

    for (int i = n; i < 2 * n; ++i) {
        int shifts = i - n;
        if (inc[i] == n) min_ops = min(min_ops, min(n - shifts, shifts + 2));
        if (dec[i] == n) min_ops = min(min_ops, min(shifts + 1, n - shifts + 1));
    }
    cout << (min_ops == 1e9 ? -1 : min_ops) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process_case();
    return 0;
}

Functional Graph State Synchronization

Given a functional graph where each node points to exactly one other node, the structure consists of trees attached to a single cycle. A greedy approach processes tree nodes first via topological sorting: if a leaf is active, it must be toggled, which flips its parent's state. Once only the cycle remains, an odd number of active nodes makes the task impossible. For an even count, nodes are paired. The starting point of the pairing matters; splitting a consecutive sequence of active nodes differently affects the total operations. Evaluating two distinct starting points guarantees the minimum operations.

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

void process_case() {
    int n;
    cin >> n;
    vector<int> state(n + 1), target(n + 1), in_deg(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;
        state[i] = c - '0';
    }
    for (int i = 1; i <= n; ++i) {
        cin >> target[i];
        in_deg[target[i]]++;
    }

    queue<int> q;
    vector<int> ops;
    for (int i = 1; i <= n; ++i) {
        if (in_deg[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (state[u]) {
            ops.push_back(u);
            state[u] ^= 1;
            state[target[u]] ^= 1;
        }
        if (--in_deg[target[u]] == 0) q.push(target[u]);
    }

    vector<bool> visited(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (!visited[i] && state[i]) {
            vector<int> cycle_nodes, cycle_states;
            int curr = i, active_count = 0;
            while (!visited[curr]) {
                cycle_nodes.push_back(curr);
                cycle_states.push_back(state[curr]);
                visited[curr] = true;
                if (state[curr]) active_count++;
                curr = target[curr];
            }
            if (active_count % 2 != 0) {
                cout << -1 << "\n";
                return;
            }
            int len = cycle_nodes.size();
            vector<int> ops1, ops2;
            auto st1 = cycle_states, st2 = cycle_states;
            for (int j = 0; j < len; ++j) {
                if (j == 0 || st1[j]) {
                    ops1.push_back(cycle_nodes[j]);
                    st1[j] ^= 1;
                    st1[(j + 1) % len] ^= 1;
                }
            }
            for (int j = 0; j < len; ++j) {
                if (j != 0 && st2[j]) {
                    ops2.push_back(cycle_nodes[j]);
                    st2[j] ^= 1;
                    st2[(j + 1) % len] ^= 1;
                }
            }
            if (ops1.size() < ops2.size()) {
                for (int x : ops1) ops.push_back(x);
            } else {
                for (int x : ops2) ops.push_back(x);
            }
        }
    }
    cout << ops.size() << "\n";
    for (int x : ops) cout << x << " ";
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process_case();
    return 0;
}