USACO 2021 January Contest Silver Division - No Time to Paint

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

While the problem might hint at more complicated techniques such as stacks, we actually only need to iterate through all the characters. Then, for the prefix and suffix check how many times you need to paint that character, something which can be done using difference arrays and prefix sums.

Source code

The source code in C++ can be seen below.

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

int N, Q;
string s;
int diffArr[100002];
int prefix[100002];
int suffix[100002];

int main() {
    cin >> N >> Q >> s;
    vector<int> arr(N + 1);
    for (int i = 1; i <= N; i++) {
        arr[i] = (s[i - 1] - 'A') + 1;
    }
    // Prefix
    for (int i = 1; i <= 26; i++) {
        bool flag = true;
        for (int j = 1; j <= N; j++) {
            if (arr[j] == i) {
                if (flag) {
                    diffArr[j]++;
                    flag = false;
                }
            }
            if (arr[j] < i) {
                flag = true;
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        prefix[i] = prefix[i - 1] + diffArr[i];
    }
    memset(diffArr, 0, sizeof(diffArr));
    // Suffix
    for (int i = 1; i <= 26; i++) {
        bool flag = true;
        for (int j = N; j >= 1; j--) {
            if (arr[j] == i) {
                if (flag) {
                    diffArr[j]++;
                    flag = false;
                }
            }
            if (arr[j] < i) {
                flag = true;
            }
        }
    }
    for (int i = N; i >= 1; i--) {
        suffix[i] = suffix[i + 1] + diffArr[i];
    }
    while (Q--) {
        int a, b;
        cin >> a >> b;
        cout << prefix[a - 1] + suffix[b + 1] << "\n";
    }
}