88. Aggressive Cows Problem

Given the positions of n stalls along a line and a number of cows c, place all c cows into stalls (at most one cow per stall) so as to maximize the minimum distance between any two cows. Print that maximum possible minimum distance.

Input: The first line contains an integer n. The second line contains n space-separated integers, the stall positions. The third line contains the integer c, the number of cows. Output: Print a single integer - the maximum possible minimum distance between any two placed cows.

2 <= c <= n <= 10^5

This is the 'maximize the minimum' variant of binary-search-on-the-answer (as opposed to 'minimize the maximum' in Painter's Partition/Book Allocation) - recognizing both variants of the pattern broadens which problems you can immediately recognize as binary-searchable.

Place cows into stalls along a line so that the smallest gap between any two cows is as LARGE as possible. Brute force: Try every possible combination of stall assignments for the c cows directly and compute the minimum gap for each - this is combinatorially expensive (choosing c stalls out of n), impractical for larger inputs. Optimised: Since 'can distance D be achieved with all c cows placed' is a MONOTONIC condition (a smaller D is always at least as easy to satisfy as a larger one), binary searching on D with an O(n) greedy placement check at each candidate reduces the combinatorial search to O(n log(range of positions)).

Consider every possible way to choose c stalls out of the n available, and for each such choice compute the minimum distance between any two of the chosen stalls, keeping track of the largest such minimum distance seen across all combinations. This directly matches the problem's definition of maximizing the minimum distance but requires examining an astronomically large number of combinations. Time: O(2^n) Space: O(c)

After sorting the stall positions, note that the greedy feasibility check, whether c cows can be placed with every consecutive gap at least d, is true for small d and false for large d, so binary search directly on d over the range from 1 to (max position - min position) instead of scanning every integer value one at a time. Each feasibility check is the same greedy placement pass as before, but only a logarithmic number of checks are needed, and the largest feasible d found is the answer. Time: O(n log(maxPosition - minPosition)) Space: O(1)

First sort the stall positions. Then, for each candidate minimum distance d starting from 1 and increasing by 1, run a greedy check: place the first cow at the first stall, and for every subsequent stall, place the next cow there only if it is at least d away from the last placed cow, counting how many cows fit. Increase d as long as the check keeps succeeding, and the last successful d is the answer; this avoids comparing arbitrary pairs of stalls but still tries every candidate distance one at a time. Time: O(n * maxPosition) Space: O(1)

1. Sort the stall positions first. 2. Binary search on the candidate minimum distance D. 3. For a candidate D, greedily check feasibility: place the first cow at the earliest stall, then place each subsequent cow at the next stall that's at least D away from the last placed cow - if all c cows fit this way, D is feasible.

Time: O(n log n) for sorting, plus O(n log(max position - min position)) for the binary search with its greedy feasibility checks. Space: O(1) extra space beyond the sorted stall positions.

Test c = n (every stall used, answer is the smallest gap between adjacent sorted stalls), c = 2 (only the two extreme stalls matter), and n = 10^5 for performance.

Be ready to explain why the greedy placement check (always place the next cow at the EARLIEST possible qualifying stall) is provably optimal for a fixed D - placing a cow any later than necessary can only ever make fitting the remaining cows harder, never easier.