USACO 2019 February Contest Silver Division - Sleepy Cow Herding

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We create prefix and suffix differences and based on this data, we can compute the maximum and minimum answers based on casework.

Source code

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

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

int main() {
    ifstream cin("herding.in");
    ofstream cout("herding.out");
    int n;
    cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    sort(v.begin(), v.end());

    // maximum
    vector<int> pref(n), suff(n);
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1];
        if (v[i] - v[i - 1] != 1) {
            if (i == 1)
                pref[i]++;
            else if (i == 2)
                pref[i] += max(0, v[i] - v[i - 1] - 1 - ((v[1] - v[0]) > 1));
            else
                pref[i] += (v[i] - v[i - 1] - 1);
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        suff[i] = suff[i + 1];
        if (v[i + 1] - v[i] != 1) {
            if (i == n - 2)
                suff[i]++;
            else if (i == n - 3)
                suff[i] += max(0, v[i + 1] - v[i] - 1 - ((v[n - 1] - v[n - 2]) > 1));
            else
                suff[i] += (v[i + 1] - v[i] - 1);
        }
    }

    int ans = max(pref[n - 1], suff[0]);

    int x = 0;
    int ansmin = ans;
    if (v[n - 2] - v[0] == n - 2 && v[n - 1] - v[n - 2] > 2)
        ansmin = 2;
    else if (v[n - 1] - v[1] == n - 2 && v[1] - v[0] > 2)
        ansmin = 2;
    else {
        for (int i = 0; i < n; i++) {
            while (x + 1 < n && v[x + 1] - v[i] < n) {
                x++;
            }
            int cnt = x - i + 1;
            ansmin = min(ansmin, n - cnt);
        }
    }
    cout << ansmin << '\n';
    cout << ans << '\n';
    return 0;
}