USACO Bronze 2018 January - Out of Place

Authors: Maggie Liu, Ryan Chou, Vikas Thoutam, David Guo

Edit This Page

Official Analysis (Java)

Video Solution

By Vikas Thoutam

Video Solution Code

Explanation

We start with our list of NN 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 KK out-of-place cows form a sequence which is sorted except for one element, so it takes exactly K−1K-1 moves to put everyone back in order (and if K≤1K \le 1, we need zero moves).

Implementation

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

C++

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {

Java

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


public class OutOfPlace {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("outofplace.in"));
		int cowNum = Integer.parseInt(read.readLine());
		int[] cows = new int[cowNum];
		for (int c = 0; c < cowNum; c++) {
			cows[c] = Integer.parseInt(read.readLine());

Python

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

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