Problem Statement
Aggressive Cows
You have a row of stalls at certain positions, and a number of cows to place in them. You want the cows spread out as far apart as possible. More exactly, you want the closest pair of cows to still be far apart. Your answer is the largest possible value of that smallest gap. The trick here is to guess the answer and check it, instead of trying every arrangement. We pick a candidate gap d and ask a simple yes or no question: can we fit all the cows so that every neighboring pair is at least d apart? If yes, we got lucky, so try a bigger gap. If no, the gap was too greedy, so try a smaller one. Narrowing a guess up or down like this is called binary search, like guessing a number between 1 and 100 by always halving the range. We do binary search on the answer itself, not on the array.
Signals to notice
Brute force first
Try all combinations of stalls — C(n,k). Combinatorial.
The key insight
Sort stalls. Binary search on the answer (minimum distance). For each candidate, greedily place cows: put cow in first stall, then next stall ≥ current + distance. If all cows placed, distance works. O(n log range).
Trace it on stalls=[1,2,4,8,9], cows=3
sort -> [1,2,4,8,9]; low=1, high=8, result=0 mid=4: place 1, then 8 (7>=4), then 9-8=1<4 -> only 2 cows. fail -> high=3 mid=2: place 1, then 4 (3>=2), then 8 (4>=2) -> 3 cows. ok -> result=2, low=3 mid=3: place 1, then 4 (3>=3), then 8 (4>=3) -> 3 cows. ok -> result=3, low=4 low=4 > high=3: loop ends return result = 3
What must stay true
If distance d works (can place all cows), any d' < d also works. This monotonicity validates binary search. Greedy placement is optimal — starting from the leftmost stall and placing as early as possible maximizes remaining room.
Shape of the loop
sort(stalls); low=1; high=stalls[-1]-stalls[0]; result=0
while low <= high:
mid = (low+high)//2
if canPlace(mid): result=mid; low=mid+1 # feasible -> try larger
else: high=mid-1 # infeasible -> shrink
return result
# canPlace(d): greedily place from stalls[0], take next stall >= last+d, count==cows?Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not sorting stalls first — the greedy placement only works on sorted positions.