USACO 2024 December Contest Silver Division - Cake Game

Problem link: here

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

The answer from the example is the smallest sum of \(3\) values in the array, so basically the sample is completely useless which leads to us thinking at more actual tests.

If Bessie builds something with too big of a sum early on, Elsie will eat it. However, she should be able to get \(\frac{n}{2}+1\) values together because of how the game works.

Given this fact, let's try to get her the smallest sum of \(\frac{n}{2}+1\) values and therefore, this will be enough to ensure the best possible outcome. In order to compute this sum, we will use sliding window.

Source code

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

#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> v(n+1);

    long long sum = 0, mini = (1LL<<60);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        sum += v[i];
    }

    long long ps = 0;
    for (int i = 1; i <= n; i++) {
        ps += v[i];
        if (i > n/2+1) {
            ps -= v[i-n/2-1];
        }
        if (i >= n/2+1) {
            mini = min(mini, ps);
        }
    }
    cout << mini << " " << sum - mini << '\n';
}

int main() {

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

    int t;
    cin >> t;

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