Official Analysis (Java)

Video Solution

By Vikas Thoutam

Explanation

We start with our list of $N$ heights and make a sorted copy of it. Then we compare the original list to the sorted list, keeping track of at which positions where they differ.

Because removing exactly one cow must make the list sorted, those $K$ out-of-place cows form a sequence which is sorted except for one element, so it takes exactly $K-1$ moves to put everyone back in order (and if $K \le 1$, we need zero moves).

Implementation

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

Copy
with open("outofplace.in") as read:
	cow_num = int(read.readline())
	cows = [int(read.readline()) for _ in range(cow_num)]

sorted_order = sorted(cows)

# The number of cows that are out of place relative to the sorted order
bad_num = 0
for i in range(len(cows)):
	if cows[i] != sorted_order[i]:
		bad_num += 1

print(bad_num - 1, file=open("outofplace.out", "w"))