USACO 2025 US Open Contest Bronze Division - It's Mooin' Time III#

Problem link: TBA

Video link: here

Problem Solution#

In order to solve this problem, we have to observe that an ideal candidate for the optimal answer has \(i\), \(j\) and \(k\) spread out throughout the range in such a way that we cover as much of the range as possible while they are spread evenly.

Because we only have \(26\) letters in the alphabet, it makes sense to iterate over the possible candidates for the 'o' and find first the rightmost letter within our range. Likewise, we can find the leftmost letter which can be a 'm' and in order to do that, we have two cases depending on whether the 'm' is the same as the 'o' or not.

After finding these two letters, we want to find the 'o' placed around the middle of this range so that we can maximize the potential product \((k - j)(j - i)\), as we already know \(k - i\) so placing \(j\) around the middle turns out to be the optimal approach.

In order to find these positions quickly, we can keep \(26\) lists, one for each letter and use binary search to find the positions required for each candidate.

The complexity of the algorithm is \(O(n + q \Sigma \log n)\), where \(\Sigma\) is the length of the alphabet, in this case \(26\).

For more details, please check the source code.

Alternatively, the binary searches can be replaced with precomputations, as described below:

In order to find the rightmost 'o', we can use a precomputation along the lines of \(prv[i][j]\) = most recent letter equal to the ith one at or before jth position - let's note this answer \(O\).
In order to find the leftmost 'm', we can also use another precomputation for the next letter equal to a certain character - \(nxt[i][j]\) = most recent letter equal to the ith one at or after jth position - let's note this answer \(M\).
In order to find the middle 'o' - we can rely on both of the precomputations to find \(nxt[i][(M+O)/2]\) = most recent letter equal to the ith one at or after (M+O)/2 th position and \(lst[i][(M+O)/2]\) = most recent letter equal to the ith one at or before (M+O)/2th position.

These precomputations speed up the complexity of the algorithm to \(O((n+q) \Sigma)\), however in practice, the binary search method is easier to implement and without much of a downside.

Source code#

The source code for the binary search solution in C++ can be seen below.

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    // precompute for each letter all positions it shows up at
    vector<vector<int>> positions(26);
    for (int i = 0; i < n; i++) {
        positions[(s[i] - 'a')].push_back(i);
    }

    for (int i = 1; i <= q; i++) {
        int L, R;
        cin >> L >> R;
        L--, R--;

        long long ans = -1;
        // iterate over the candidates for the last letter (the two o's). for each of them find the leftmost m and the most suitable o in the middle.
        for (int last_letter = 0; last_letter < 26; last_letter++) {
            int posm = -1;
            int poso1 = -1;
            int poso2 = -1;
            // find leftmost letter not equal to the last letter
            if ((s[L] - 'a') != last_letter) {
                posm = L;
            }
            else {
                // binary search the leftmost letter not equal to last_letter
                for (int candidate = 0; candidate < 26; candidate++) {
                    if (candidate != last_letter) {
                        int l = 0;
                        int r = positions[candidate].size() - 1;
                        while (l <= r) {
                            int m = (l+r) / 2;
                            if (positions[candidate][m] < L) {
                                l = m+1;
                            }
                            else {
                                if (posm == -1) {
                                    posm = positions[candidate][m];
                                }
                                else {
                                    posm = min(posm, positions[candidate][m]);
                                }
                                r = m-1;
                            }
                        }
                    }
                }
            }
            // find rightmost letter equal to last letter using binsearch
            int l = 0;
            int r = positions[last_letter].size() - 1;
            while (l <= r) {
                int m = (l+r) / 2;
                if (positions[last_letter][m] <= R) {
                    poso2 = positions[last_letter][m];
                    l = m+1;
                }
                else {
                    r = m-1;
                }
            }
            if (posm != -1 && poso2 != -1) {
                // find letter closest to the middle of the range [posm, poso2] using binsearch
                l = 0;
                r = positions[last_letter].size() - 1;
                int middle = (posm + poso2) / 2;
                while (l <= r) {
                    int m = (l+r) / 2;
                    if (positions[last_letter][m] <= middle) {
                        poso1 = m;
                        l = m+1;
                    }
                    else {
                        r = m-1;
                    }
                }
                if (poso1 != -1 && positions[last_letter][poso1] >= posm) {
                    ans = max(ans, 1LL * (positions[last_letter][poso1] - posm) * (poso2 - positions[last_letter][poso1]));
                }
                if (poso1 + 1 < (int) positions[last_letter].size() && positions[last_letter][poso1+1] >= posm) {
                    ans = max(ans, 1LL * (positions[last_letter][poso1+1] - posm) * (poso2 - positions[last_letter][poso1+1]));
                }
            }
        }

        if (ans == 0) {
            ans = -1;
        }
        cout << ans << '\n';
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;

    while (t--) {
        solve();
    }
    return 0;
}