Official Analysis (C++)

Video Solution

By Melody Yu

Video Solution Code

Explanation

Since there are only 88 cows, there are 8!=403208! = 40320 distinct possible orderings, which is small enough for us to try all of them and still pass the problem in time.

If we generate them in alphabetical order and find an ordering that satisfies all the given constraints, then we can stop and print out the answer right then and there.

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