USACO 2024 US Open Contest Silver Division - The 'Winning' Gene

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can create the LCP matrix of the string. We notice that we can solve the problem by fixing a \(p\) (starting position) and an \(l\), searching for \(k\). With two pointers, we can find the positions to which a substring of size \(k\) (left + right) can extend, knowing that, for the starting position \(p\) to appear in sets of \((k, l)\) there must not be another string of length \(l\) in the substring of length \(k\) that is lexicographically smaller than the one of length \(l\) starting from \(p\).

Source code

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

#include <bits/stdc++.h>

using namespace std;
const int NMAX = 3e3;
int n;
string s;
int lcp[NMAX + 5][NMAX + 5], rez[NMAX + 5][NMAX + 5], cnt[NMAX + 5];
int compare(int i, int j, int k) {
    if (lcp[i][j] >= k)
        return 0;
    if (i + lcp[i][j] == n)
        return -1;
    if (j + lcp[i][j] == n)
        return 1;
    char a = s[i + lcp[i][j]];
    char b = s[j + lcp[i][j]];
    if (a < b)
        return -1;
    return 1;
}
int main() {
    cin >> n >> s;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (s[i] == s[j])
                lcp[i][j] = (s[i] == s[j]) + lcp[i + 1][j + 1];
        }
    }
    for (int p = 0; p < n; p++) {
        int b[NMAX + 5] = {0}, a[NMAX + 5] = {0};
        int b_cand = p + 1, a_cand = p - 1;
        for (int l = n; l >= 1; l--) {
            while (b_cand < n && compare(p, b_cand, l) <= 0)
                b_cand++;
            b[l] = min(b_cand + l, n + 1);
        }
        for (int l = 1; l <= n; l++) {
            while (a_cand >= 0 && compare(p, a_cand, l) < 0)
                a_cand--;
            a[l] = a_cand + 1;
        }
        for (int l = 1; l <= n; l++) {
            if (l + p > n)
                continue;
            rez[l][min(b[l] - a[l] - 1, n)]++;
        }
    }
    for (int l = 1; l <= n; l++) {
        int sum = 0;
        for (int k = n; k >= l; k--) {
            sum += rez[l][k];
            cnt[sum]++;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << cnt[i] << "\n";
    return 0;
}