Solution Explanation Implementation Video Solution

Solution

Explanation

We can think about this problem by looking at the end of the array of cows.

Notice that if the last $i$ elements in the array are sorted in increasing order, FJ can fully sort the cows in $n-i$ time steps. This is because the first $n-i$ elements are still to be sorted.

Thus, we can find the last unsorted cow and output its position.

Implementation

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

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	freopen("sleepy.in", "r", stdin);

	int n;
	cin >> n;
	vector<int> cows(n);
	for (int &c : cows) { cin >> c; }

Java

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

public class SleepyCowSorting {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("sleepy");
		int n = io.nextInt();
		int[] cows = new int[n];

		for (int i = 0; i < n; i++) { cows[i] = io.nextInt(); }

Python

file_in = open("sleepy.in")
data = file_in.read().strip().split("\n")

n = int(data[0])
cows = list(map(int, data[1].split(" ")))

ans = 0
# Find the number of strictly increasing values at the end of the list
for i in range(n - 1, 0, -1):
	if cows[i] < cows[i - 1]:
		ans = i
		break

print(ans, file=open("sleepy.out", "w"))

Video Solution

By Vikas Thoutam

Video Solution Code

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!