Official Analysis (C++)

Video Solution 1

By Hannah Ying

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

Video Solution 2

By Melody Yu

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

Solution

Explanation

Minimum

We will generally use a two-pointer sliding window technique on the sorted cows array to find the $length-N$ window containing the most cows (i.e fewest empty spaces). The minimum value is the number of empty spaces in that window. However, there is an edge case: if $N-1$ cows are already consecutive but the last cow is far away, we need $2$ moves instead of $1$ since we have to bridge the gap first.

Maximum

It is similar to the bronze version of this problem. We will consider the total number of empty cells between all cows, then subtract the gap we want to sacrifice. Here, the gaps are $(herd[1] - herd[0])$and $(herd[N-1] - herd[N-2])$. To get the maximum value, we sacrifice the smaller of the two gaps.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
with open("herding.in") as read:
	n = int(read.readline())
	herd = sorted(int(read.readline()) for _ in range(n))

min_moves = float("inf")
if herd[n - 2] - herd[0] == n - 2 and herd[n - 1] - herd[n - 2] > 2:
	min_moves = 2
elif herd[n - 1] - herd[1] == n - 2 and herd[1] - herd[0] > 2:
	min_moves = 2
else: