USACO Silver 2020 US Open - Social Distancing

Official Analysis

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

Explanation

Observe that for any distance, if it is not possible for all the cows to stand on grass with the specified distance, then it is not possible for any distance greater than said distance. Furthermore, while it may be difficult to calculate $D$ directly (one does not even know how to approach such a problem), it is not as difficult to check if a certain proposed distance is valid. This makes for a perfect binary search problem.

We need to check for a specified minimum distance between cows of $d$, if all cows are able to be placed on grass. This can be done by iterating through the sorted (mutually-disjoint) intervals and placing the cows optimally.

Consider the first interval. It is most efficient to place the cow on the left-most edge of the interval to allow the most room for other cows. Then, if there is space in the same interval $d$ distance away, we place the next cow. We repeat until there is no more room in the current interval, where we switch to the next interval. We again place our cow as left as possible, while still keeping at least $d$ distance from the previous cow (If we cannot place a cow in this interval we skip it). We repeat this process until all cows have been placed or there are no more intervals. If there are no more intervals and there are cows left unplaced, then the proposed distance is invalid.

Implementation

Time Complexity: $\mathcal{O}((N+M)\log (\texttt{maxDist}))$

Copy
#include <bits/stdc++.h>

using namespace std;

void setIO(string prob = "") {
	if (!prob.empty()) {
		freopen((prob + ".in").c_str(), "r", stdin);
		freopen((prob + ".out").c_str(), "w", stdout);
	}
}

Copy
with open("socdist.in", "r") as r:
	n, m = map(int, r.readline().split())
	intervals = [tuple(map(int, r.readline().split())) for _ in range(m)]
	intervals.sort()


def possible_placement(d: int) -> bool:
	cows = n
	prev_cow_location = intervals[0][0] - d

Copy
import java.io.*;
import java.util.*;

public class SocDist {
	static class Pair implements Comparable<Pair> {
		long first, second;

		public Pair(long x, long y) {
			first = x;
			second = y;