USACO 2024 February Contest Silver Division - Moorbles

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

It's best to take a prefix and see if we can continue with it for a correct solution. With the help of some partial sum precalculations, we can see the minimum \(n\) we will reach along the way, until the end. If the minimum \(n>0\), then we can continue with the solution, otherwise we have to change it. We can calculate these things in linear time.

Source code

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

#include <bits/stdc++.h>
using namespace std;
int arr[300000][4];
int oddCost[300000];
int evenCost[300000];
int bestCost[300000];
int maxSuffix[300000];
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        for (int i = 0; i < m; i++) {
            int odds = 0;
            int evens = 0;
            int maxOdd = -1;
            int maxEven = -1;
            int minOdd = 1001;
            int minEven = 1001;
            for (int j = 0; j < k; j++) {
                cin >> arr[i][j];
                if (arr[i][j] % 2 == 0) {
                    // even
                    evens++;
                    maxEven = max(maxEven, arr[i][j]);
                    minEven = min(minEven, arr[i][j]);
                } else {
                    // odd
                    odds++;
                    maxOdd = max(maxOdd, arr[i][j]);
                    minOdd = min(minOdd, arr[i][j]);
                }
            }

            if (evens == k) {
                // all even
                evenCost[i] = minEven;
                oddCost[i] = -1 * maxEven;
            } else if (odds == k) {
                // all odd
                oddCost[i] = minOdd;
                evenCost[i] = -1 * maxOdd;
            } else {  // mix
                evenCost[i] = -1 * maxOdd;
                oddCost[i] = -1 * maxEven;
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            bestCost[i] = max(oddCost[i], evenCost[i]);
            if (i != m - 1) bestCost[i] += bestCost[i + 1];
            maxSuffix[i] = bestCost[i];
            if (i != m - 1) maxSuffix[i] = max(maxSuffix[i], maxSuffix[i + 1]);
            // suffix on best possible cost
        }
        int cur = n;
        bool quit = false;
        for (int i = 0; i < m; i++) {
            cur += max(oddCost[i], evenCost[i]);
            if (cur <= 0) {
                cout << "-1\n";
                quit = true;
                break;
            }
        }
        if (quit) {
            continue;
        }

        // first check if it's possible
        if (n + bestCost[0] <= 0) {
            // no matter, what, impossible.
            cout << "-1\n";
            continue;
        }
        for (int i = 0; i < m; i++) {
            if (evenCost[i] >= oddCost[i]) {
                // even is literally better, just do that
                cout << "Even";
                if (i != m - 1) {
                    cout << " ";
                }
                n += evenCost[i];
                continue;
            }

            // now we have that even is worse than odd
            // check if its possible to take even
            int chooseEven = n + evenCost[i];
            if (i != m - 1) {
                chooseEven += bestCost[i + 1];
            }
            int choose2 = chooseEven;
            if (i != m - 1) {
                choose2 -= maxSuffix[i + 1];
            }

            if (chooseEven > 0 && (n + evenCost[i]) > 0 && (choose2) > 0) {
                // ends in positive and is currently positive too
                cout << "Even";
                n += evenCost[i];
            } else {
                cout << "Odd";
                n += oddCost[i];
            }
            if (i != m - 1) {
                cout << " ";
            }
        }
        cout << "\n";
    }
}