USACO 2023 December Contest Silver Division - Bovine Acrobatics

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can sort the weights and towers in descending order of the weight and we can use an algorithm akin in style to a standard breadth first search, as we go through the heaviest towers at any given step while also going through weights.

Basically, we want to place the cows in towers that have on top of them heavier cows and if we still have towers we haven't used yet, then pick up whatever is left and start as many towers as needed.

This algorithm works fast enough because for any distinct cow, we will create only one entry in the queue which stores how many towers are the same in behavior in terms of the lowest weighted cow on top.

The complexity of the algorithm will be \(O(n \log n)\) as we have to sort the cows at the beginning by their weight.

Source code

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> cows;
    for (int i = 0; i < n; i++) {
        int w, a;
        cin >> w >> a;
        cows.push_back({w, a});
    }
    sort(cows.rbegin(), cows.rend());
    long long ans = 0, sum = m;
    queue<pair<int, long long>> Q;
    for (int i = 0; i < n; i++) {
        int w = cows[i].first;
        long long c = cows[i].second;
        while (!Q.empty() && Q.front().first - k >= w) {
            sum += Q.front().second;
            Q.pop();
        }
        long long pc = min(sum, c);
        if (pc > 0) {
            Q.push({w, pc});
            sum -= pc;
            ans += pc;
        }
    }
    cout << ans << '\n';
    return 0;
}