USACO 2024 US Open Contest Silver Division - Bessie's Interview

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Maintain a min‑heap (or set) of \((next_free_time, farmer_id)\) for the K interviewers, repeatedly popping all entries with the smallest time \(T\) to form a batch, assigning each to the next cow (stopping when you assign cow \(N+1\) at time \(T\)), and recording each batch of farmer IDs.

Finally, traverse these batches in reverse: mark every farmer in the last batch as a candidate, then for each earlier batch include any farmer who shares a batch with an already marked farmer.

Source code

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

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

vector<int> v;

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

    int n, k;
    cin >> n >> k;

    v.resize(n + 1);

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

    set<pair<long long, int> > s;
    for (int i = 1; i <= k; i++) 
        s.insert({v[i], i});

    vector<vector<int> > paths;
    for (int i = k + 1; i <= n + 1;) {
        vector<pair<long long, int> > vv;
        pair<long long, int> xx = *s.begin();
        vv.push_back(xx);
        s.erase(xx);

        while (!s.empty()) {
            xx = *s.begin();
            if (xx.first == vv[0].first) {
                vv.push_back(xx);
                s.erase(xx);
            } 
            else
                break;
        }

        vector<int> tv;
        for (int i = 0; i < vv.size(); i++) 
            tv.push_back(vv[i].second);
        paths.push_back(tv);

        if (i == n + 1) {
            cout << vv[0].first << '\n';
            break;
        }

        while (!vv.empty()) {
            xx = vv.back();
            vv.pop_back();
            if (i <= n) {
                xx.first += v[i];
                i++;
            }
            s.insert(xx);
        }
    }

    string ans;
    for (int i = 0; i < k; i++) 
        ans += '0';
    for (int i = paths.size() - 1; i >= 0; i--) {
        if (i == (int)paths.size() - 1) {
            for (int j = 0; j < paths[i].size(); j++) 
                ans[paths[i][j] - 1] = '1';
        } 
        else {
            bool isOne = 0;
            for (int j = 0; j < paths[i].size(); j++)
                if (ans[paths[i][j] - 1] == '1') 
                    isOne = 1;
            if (isOne)
                for (int j = 0; j < paths[i].size(); j++) 
                    ans[paths[i][j] - 1] = '1';
        }
    }
    cout << ans;
    return 0;
}