USACO Bronze 2019 December - Livestock Lineup

Authors: Benjamin Qi, Kevin Sheng, Melody Yu, Ryan Chou

Edit This Page

Official Analysis (C++)

Video Solution

By Melody Yu

Video Solution Code

Explanation

Since we have 88 cows, we can build every single permutation of them, which comes out to 4032040320 possible orderings.

For each permutation we then check if it's valid. To ensure that the alphabetically earliest ordering is selected, though, we must iterate in lexicographical order.

Implementation

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

C++

#include <bits/stdc++.h>


using namespace std;


const int RESTRICT_LEN = 6;
// list of cows, in alphabetical order
const vector<string> COWS = {"Beatrice", "Belinda", "Bella",     "Bessie",
                             "Betsy",    "Blue",    "Buttercup", "Sue"};


vector<vector<string>> orderings;

Java

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


class Pair<T, U> {
	T first;
	U second;


	public Pair(T first, U second) {
		this.first = first;
		this.second = second;

Python

from typing import List


# list of cows, in alphabetical order
COWS = ["Beatrice", "Belinda", "Bella", "Bessie", "Betsy", "Blue", "Buttercup", "Sue"]


orderings = []




def build(ordering: List[str]):
	# finished building permutation

O(N)\mathcal{O}(N) Solution With Graphs

This solution is covered in the Introduction to Graphs module.

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