USACO 2020 US Open Contest Silver Division - Social Distancing

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main idea consists in sorting the intervals and doing binary search over the answer by greedily choosing the earliest possible position for each cow.

Source code

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

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

int n, m;
vector<pair<int, int> > intervals;

int main() {
    ifstream cin("socdist.in");
    ofstream cout("socdist.out");

    cin >> n >> m;
    intervals.resize(m);

    for (int i = 0; i < m; i++) 
        cin >> intervals[i].first >> intervals[i].second;

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

    int L = 0;
    int R = 1e9;
    int ans = 0;
    while (L <= R) {
        int mid = (L + R) / 2;
        int pos = -2e9;
        int countCows = 0;
        for (int i = 0; i < m; i++) {
            while (countCows < n && max(intervals[i].first, pos + mid) <= intervals[i].second) {
                pos = max(intervals[i].first, pos + mid);
                countCows++;
            }
        }
        if (countCows == n)
            ans = mid, L = mid + 1;
        else
            R = mid - 1;
    }

    cout << ans;
    return 0;
}