In today's contest, problems C and D were very similar because they required iterating an array based on ranges of equal values. After the contest ended, I opened other participants' solutions and saw long, complicated codes, when both problems were actually simple. Therefore I decided to share a very easy technique I like to use in these situations. I wasn't sure about writing this blog, since I believed this method was too obvious. But after seeing that many people struggled today, I decided it may turn out helpful.

Take the classic problem of string compression: Given a string str, return a vector V of pairs (letter, frequency) that represents the string. For example "aaacbbab" would yield [(a, 3), (c, 1), (b, 2), (a, 1), (b, 1)].

vector<pair<char, int>> compress(const string &str){
    vector<pair<char, int>> ret;
    for(int i = 0, j = 0; i < str.size(); i = j){
        for(; j < str.size() && str[i] == str[j]; j++);
        
        //range operation:
        
        ret.push_back(make_pair(str[i], j - i));
    }
    return ret;
}

The key of this method is that it encapsulates the range calculation, so that you just need to adapt the "range operation" indicated in the function. Note that the size of the actual range is j — i (furthermore, the range is [i, j) ) and the value of the range is str[i]. These two observations sound trivial, but you can really take advantage of them. Here is how this method works for problem C of today:

typedef long long ll;
ll getMaxSum(int n, int k, int *a, const string &s){
    ll sum = 0;
    for(int i = 0, j = 0; i < n; i = j){
        priority_queue<int> pq;
        for(; j < n && s[i] == s[j]; j++) pq.push(a[j]);
        //range operation:
        for(int r = 0; pq.size() && r < k; r++) {sum += pq.top(); pq.pop();}
    }
    return sum;
}

Here is the same technique applied on problem D:

int getX(int n, const vector<vector<char>> &A){
    int ans = 0;
    for(int u = 0; u < n; u++)
        for(int i = 0, j = 0; i < n; i = j){
            for(; j < n && A[u][i] == A[u][j]; j++);
            //range operation:
            ans = __gcd(ans, j - i);
        }
    for(int u = 0; u < n; u++){
        for(int i = 0, j = 0; i < n; i = j){
            for(; j < n && A[i][u] == A[j][u]; j++);
            //range operation:
            ans = __gcd(ans, j - i);
        }
    }
    return ans;
}

Again, the advantage of this technique is that it separates the "range operation" nicely, so you only have to focus on the problem logic, and not in details of the actual range distinctions. I hope you find it useful.