USACO 2024 January Contest Silver Division - Cownpetency

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We notice that for a prefix of the vector we will need to have a maximum value, and this to be the maximum on a longer prefix up to a certain position, based on the given pair relations.

Thus, we will need to handle this case and, for a position where we put a new element, we must check that it is greater than any element in the prefix in its (if any) longest pair.

If the conditions are met, we have a solution. To modify the maximum of a prefix, we can put a value on the rightmost element equal to 0 on the respective prefix.

For more details, check the source code below.

Source code

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

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

using ll = long long;
#define pb push_back
#define int ll

void solve() {
    int n, q, c, i, j, a, h, possible_max, mx, idx;

    cin >> n >> q >> c;

    vector<int> score(n + 1);
    for (i = 1; i <= n; i++) {
        cin >> score[i];
    }

    vector<int> same(n + 1), inc(n + 1);
    // same[i] > 0 => pref_mx[i] = pref_mx[i - 1]
    // inc[i] == 1 => pref_mx[i] > pref_mx[i - 1]
    inc[1] = 1;
    while (q--) {
        cin >> a >> h;
        // for a (a, h) i want to have s[h] > max({s[1], s[2], ..., s[a]})
        // s[1] = max(s[1], s[2]) = max({s[1], s[2], s[3]}) = ... = max({s[1], s[2],
        // ..., s[a]})
        same[a + 1]++;
        same[h]--;
        inc[h] = 1;  // h > max({s[1], s[2], ..., s[a]})
    }
    for (i = 1; i <= n; i++) {
        same[i] += same[i - 1];
        if (same[i] > 0 && inc[i] == 1) {
            cout << "-1\n";
            return;
        }
    }

    possible_max = 0;
    for (i = n; i >= 1; i--) {
        if (!same[i]) {
            possible_max = 0;
            continue;
        }
        possible_max = max(possible_max, score[i]);
        if (score[i - 1] == 0) {  // unknown yet
            continue;
        }
        // propagate
        if (possible_max > score[i - 1]) {
            same[i - 1] = same[i];
        }

        if (same[i] > 0 && inc[i] == 1) {
            cout << "-1\n";
            return;
        }
        if (same[i - 1] > 0 && inc[i - 1] == 1) {
            cout << "-1\n";
            return;
        }
    }

    possible_max = 0;
    for (i = 1; i <= n; i++) {
        mx = max(score[i], 1LL);  // score[i] = 0 => unknown
        if (inc[i]) {
            // inc[i] => pref_mx[i] > pref_mx[i - 1]
            mx = max(mx, possible_max + 1);
        }

        j = i;
        // same[j + 1] => pref_mx[j + 1] = pref_mx[j]
        while (j <= n - 1 && same[j + 1] > 0) {
            mx = max(mx, score[++j]);
        }
        if (score[i] == 0) {
            // it is unknown
            if (max(mx, possible_max) == mx) {
                score[i] = mx;
            } else {
                score[i] = 1;  // for the lexicographically smallest string
            }
        }
        for (idx = i + 1; idx <= j; idx++) {
            if (score[idx] > 0) {
                continue;
            }
            score[idx] = 1;  // lexicographically smallest
        }
        possible_max = max(possible_max, mx);
    }

    if (possible_max > c) {
        cout << "-1\n";
        return;
    }

    vector<int> pref_mx(n + 1, 0);
    for (i = 1; i <= n; i++) {
        pref_mx[i] = max(pref_mx[i - 1], score[i]);

        if (same[i] && pref_mx[i] != pref_mx[i - 1]) {
            cout << "-1\n";
        }
        if (inc[i] && pref_mx[i] <= pref_mx[i - 1]) {
            cout << "-1\n";
            return;
        }
    }

    for (i = 1; i <= n; i++) {
        cout << score[i];
        if (i != n) {
            cout << " ";
        }
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}