USACO Bronze 2019 January - Sleepy Cow Sorting

Authors: Ananth Kashyap, Brad Ma, Vikas Thoutam

Edit This Page

Official Analysis

Video Solution

By Vikas Thoutam

Video Solution Code

Explanation

We can think about this problem by looking at the end of the array of cows. Notice that if the last ii elements in the array are sorted in increasing order, FJ can fully sort the cows in n−in-i time steps. This is because the first n−in-i elements are still to be sorted. Thus, we can find the last unsorted cow and output its position.

Implementation

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

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):

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(); }

C++

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


int cows[105];


int main() {
	freopen("sleepy.in", "r", stdin);
	freopen("sleepy.out", "w", stdout);
	int n;
	cin >> n;

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!

Join Forum