O(N) Solution for Problem 2. Milking Order (USACO Bronze – Greedy)

Resources & Problemsets
#1

Hi everyone! :wave:

The problem: Milking Order (USACO Bronze – Greedy) —
also appears as a bonus question in the USACO Guide under the Greedy section.

Since I noticed there wasn’t any officially provided O(N) code or detailed explanation for it, I’m sharing my accepted solution here in case it helps others understand the logic better.

  • Hint 1: If cow 1 already has a fixed position in the milking order, that’s directly the answer.
  • Hint 2: What if cow 1 appears in the social hierarchy sequence? Think about how that affects where the entire sequence should be placed.
  • Hint 3:
  • If cow 1 does not appear in the hierarchy sequence, greedily try to place the hierarchy as far right as possible (so cow 1 can go earlier).
  • If cow 1 does appear in the hierarchy sequence, greedily try to place the hierarchy as early as possible (so cow 1 gets the earliest valid spot).

My O(N) Solution (AC)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nline "\n"

void solve(){
    ll n,m,k;
    cin>>n>>m>>k;
    vector<ll> cows(m);
    for(auto &it:cows)cin>>it;
    vector<ll> time(n+1,-1); // at time[i] = which cow is milked
    map<ll,ll> done; // cow -> fixed position

    for(int i=0;i<k;i++){
        ll x,y;
        cin>>x>>y;
        time[y]=x;
        done[x]=y;
    }

    // If cow 1 already has a fixed position
    if(done.find(1)!=done.end()){
        cout<<done[1]<<nline;
        return;
    }

    bool inHierarchy=false;
    for(auto it:cows) if(it==1) inHierarchy=true;

    if(!inHierarchy){
        // Place hierarchy as right as possible
        ll i=n, j=m-1;
        while(i>=1 && j>=0){
            if(time[i]!=-1){
                if(time[i]==cows[j]) j--;
                i--;
                continue;
            }
            if(done.find(cows[j])!=done.end()){
                i=done[cows[j]]-1;
                j--;
                continue;
            }
            time[i]=cows[j];
            i--;
            j--;
        }

        for(ll x=1;x<=n;x++){
            if(time[x]==-1 || time[x]==1){
                cout<<x<<nline;
                return;
            }
        }
    }
    else{
        // Cow 1 is in hierarchy → place as left as possible
        ll i=1, j=0;
        while(i<=n && j<m){
            if(time[i]!=-1){
                if(time[i]==cows[j]) j++;
                i++;
                continue;
            }
            if(done.find(cows[j])!=done.end()){
                i=done[cows[j]]+1;
                j++;
                continue;
            }
            time[i]=cows[j];
            i++;
            j++;
        }

        for(ll i=1;i<=n;i++){
            if(time[i]==1){
                cout<<i<<nline;
                return;
            }
        }
    }
}

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

    #ifndef ONLINE_JUDGE
    freopen("milkorder.in", "r", stdin);
    freopen("milkorder.out", "w", stdout);
    #endif

    solve();
    return 0;
}

Key Insight:

Cow 1 can either belong to the hierarchy or not — that single distinction changes whether we place the hierarchy earliest or latest to minimize cow 1’s position.