A. Be Positive

Count how many elements are negative. If the amount is odd, flip one more element so the product becomes positive.

void solve() {
    int n; cin >> n;
    int neg = 0;
    for (int i = 0; i < n; ++i) {
        int v; cin >> v;
        if (v < 0) ++neg;
    }
    cout << (neg & 1 ? neg + 1 : neg) << '\n';
}

B. Unconvenitonal Pairs

Sort the array and pair adjacent elements. The answer is the largest difference among these pairs.

void solve() {
    int n;; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(a.begin(), a.end());
    int best = 0;
    for (int i = 0; i + 1 < n; i += 2)
        best = max(best, a[i + 1] - a[i]);
    cout << best << '\n';
}

C. MEX Rose

To make the MEX equal k, every value k must be removed, and every value 0..k-1 must appear atleast once. The answer is the maximum between the number of k's and the amount of missing values in 0..k-1.

void solve() {
    int n, k; cin >> n >> k;
    vector<int> freq(n + 2);
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        ++freq[x];
    }
    int miss = 0;
    for (int v = 0; v < k; ++v) if (!freq[v]) ++miss;
    cout << max(freq[k], miss) << '\n';
}

D. A and B

Collect positions of each letter, then compute the cost to move all occurrences of that letter into a contiguous block by choosing the median position. The minimum cost over the two letters is the answer.

void solve() {
    int n; string s; cin >> n >> s;
    long long ans = 1e18;
    for (char c : {'a', 'b'}) {
        vector<int> pos;
        for (int i = 0; i < n; ++i)
            if (s[i] == c) pos.push_back(i);
        if (pos.empty()) continue;
        int m = pos.size();
        int med = pos[m / 2];
        long long cost = 0;
        for (int i = 0; i < m; ++i)
            cost += abs(pos[i] - (med - m / 2 + i));
        ans = min(ans, cost);
    }
    cout << ans << '\n';
}

E. Hidden Knowledge of the Ancients

Slide a window while maintaining a frequency map. For each left endpoint, find the smallest right endpoint that contains at least k distinct colors, then extend to the furthest right that still keeps exactly k colors. Count valid right endpoints within the given range.

void solve() {
    int n, k, L, R; cin >> n >> k >> L >> R;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    long long res = 0;
    map<int, int> cnt;
    int l = 0, r = 0, distinct = 0;
    for (int i = 0; i < n; ++i) {
        while (r < n && distinct < k) {
            if (++cnt[a[r++]] == 1) ++distinct;
        }
        int low = max(l, i + L - 1);
        int high = min(r - 1, i + R - 1);
        if (distinct == k && low <= high) res += high - low + 1;
        if (--cnt[a[i]] == 0) --distinct;
    }
    cout << res << '\n';
}

F. Nezuko in the Clearing

Binary-search the number of rests x. Each rest splits the journey into x+1 equal or almost-equal segments. Compute the total damage and compare with available health.

void solve() {
    long long h, d; cin >> h >> d;
    int lo = 0, hi = d, ans = d;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        long long segments = mid + 1;
        long var len = d / segments;
        long var extra = d % segments;
        long var dmg = len * (len + 1) / 2 * segments + extra * (len + 1);
        if (dmg < h + mid) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    cout << ans + d << '\n';
}

G. Buratsuta 3

Find all values whose frequency in [l,r] is greater than (r-l+1)/3. Three approaches are viable:

1. Square-root decomposition: split by threshold B ≈ n^{3/5}.
2. Random sampling: pick 50 random indices and verify their counts.
3. Segment tree with Misra-Gries: each node stores up to two candidates with counts, merged via the Misra-Gries algorithm.

All solutions use coordinate compression and binary search to count occurrences quickly.