A - Shrinking

Given a string s, determine the minimum number of operasions required to make all characters identical. Each operation reduces the string length by one by selecting characters from adjacent positions.

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

int main() {
    string input;
    cin >> input;
    int length = input.size();
    int min_operations = 1e9;

    for (char target = 'a'; target <= 'z'; ++target) {
        vector<int> current, next;
        for (char c : input) {
            current.push_back(c == target ? 1 : 0);
        }
        
        int operations = 0;
        while (true) {
            bool all_match = true;
            for (int val : current) {
                if (val == 0) {
                    all_match = false;
                    break;
                }
            }
            if (all_match) break;

            next.clear();
            for (size_t i = 0; i < current.size() - 1; ++i) {
                next.push_back(max(current[i], current[i+1]));
            }
            current = next;
            operations++;
        }
        min_operations = min(min_operations, operations);
    }
    cout << min_operations << endl;
    return 0;
}

B - Colorful Hats

Given an array a where each element represents the number of distinct hat colors observed by cat i (excluding itself), determine if a valid hat color assignment exists.

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

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

    sort(a.begin(), a.end());
    int min_val = a[0], max_val = a.back();
    
    if (min_val + 1 < max_val) {
        cout << "No";
        return 0;
    }

    if (min_val == max_val) {
        if (min_val == n-1 || n >= 2*min_val) {
            cout << "Yes";
        } else {
            cout << "No";
        }
        return 0;
    }

    int count_min = 0, count_max = 0;
    for (int val : a) {
        if (val == min_val) count_min++;
        else count_max++;
    }

    if (max_val >= count_min + 1 && max_val <= count_min + count_max / 2) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

C - +/- Rectangle

Construct a matrix where the total sum is positive, but every h×w submatrix has a negative sum. Special handling is required when dimensions are perfectly divisible.

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

int main() {
    int n, m, h, w;
    cin >> n >> m >> h >> w;
    int matrix[505][505] = {};

    if (n % h != 0 || m % w != 0) {
        // Handle row-based pattern
        for (int i = 1; i <= n; ++i) {
            if (i % h != 0) {
                fill(matrix[i]+1, matrix[i]+m+1, 1e6);
            } else {
                fill(matrix[i]+1, matrix[i]+m+1, -1e6 * (h-1) - 1);
            }
        }
    } else {
        // Handle column-based pattern
        for (int j = 1; j <= m; ++j) {
            if (j % w != 0) {
                for (int i = 1; i <= n; ++i) {
                    matrix[i][j] = 1e6;
                }
            } else {
                for (int i = 1; i <= n; ++i) {
                    matrix[i][j] = -1e6 * (w-1) - 1;
                }
            }
        }
    }

    cout << "Yes" << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}