Problem A - String Transformation

Given a binary string s of length n, and an initially empty string t, you can either append the suffix of s to t, or append the suffix of t back to s. Determine the minimum number of operations needed so that all characters in s are '0' and all characters in t are '1'.

To solve this, count the transitions between '0' and '1' in the string. Each transition requires one operation.

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        int changes = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] != s[i-1]) {
                changes++;
            }
        }
        // If the first character is '1', it also counts as a change.
        if (s[0] == '1') {
            changes++;
        }
        cout << changes << "\n";
    }
    return 0;
}

Problem B - Array Score Optimization

You're given an array a of size n. The score of the array is defined as its length minus the number of unique elements. You can remove any contiguous subarray to maximize the score. In case of ties, choose the removal that results in the smallest possible array length.

The optimal strategy involves removing the longest contiguous subarray where each element appears exactly once.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n+1);
        unordered_map<int, int> freq;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            freq[a[i]]++;
        }

        int left = 0, right = 0;
        int current_left = 0, current_right = 0;
        for (int i = 1; i <= n; ++i) {
            if (freq[a[i]] == 1) {
                if (current_left == 0) {
                    current_left = i;
                }
                current_right = i;
            } else {
                if (current_right - current_left > right - left) {
                    left = current_left;
                    right = current_right;
                }
                current_left = current_right = 0;
            }
        }

        if (current_right - current_left > right - left) {
            left = current_left;
            right = current_right;
        }

        if (left == 0) {
            cout << "0\n";
        } else {
            cout << left << " " << right << "\n";
        }
    }
    return 0;
}

Problem C - Maximize Coins and Score

You have an array a of length n with no zeros. Starting with a score of zero, repeatedly perform the following operation until the array is empty: Select an index i and gain |a[i]| coins. If a[i] is negative, gain additional points equal to |a[i]| and remove the prefix up to i; otherwise, gain points equal to a[i] and remove the suffix starting from i.

A greedy approach works here: always select the leftmost positive number or the rightmost negative number.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n+1);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }

        vector<int> prefix_positive(n+1, 0), suffix_negative(n+1, 0);
        int total_pos = 0, total_neg = 0;

        for (int i = 1; i <= n; ++i) {
            if (a[i] > 0) {
                total_pos += a[i];
            }
            prefix_positive[i] = total_pos;
        }

        for (int i = n; i >= 1; --i) {
            if (a[i] < 0) {
                total_neg -= a[i];
            }
            suffix_negative[i] = total_neg;
        }

        int max_score = 0;
        for (int i = 1; i <= n; ++i) {
            max_score = max(max_score, prefix_positive[i] + suffix_negative[i]);
        }

        cout << max_score << "\n";
    }
    return 0;
}

Problem D - Slime Eating Simulation

Slimes can eat other slimes under certain conditions. Given a sequence of slimes with weights and multiple queries, simulate how many slimes a new slime (added at the end) can consume based on weight constraints.

This problem requires maintaining a stack-like structure to efficiently process each query.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<long long> slimes(n);
    for (int i = 0; i < n; ++i) {
        cin >> slimes[i];
    }

    int q;
    cin >> q;
    while (q--) {
        long long x;
        cin >> x;
        int eaten = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (x >= slimes[i]) {
                x += slimes[i];
                eaten++;
            } else {
                break;
            }
        }
        cout << eaten << "\n";
    }
    return 0;
}