USACO 2019 December Contest Bronze Division - Livestock Lineup

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Just a simple brute force problem. Make sure to sort the cows alphabetically and try every possible permutation, while checking also if positions are adjacent.

Source codes

The source codes in C++ and Python can be seen below.

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

string cows[8] = {"Beatrice", "Belinda", "Bella", "Bessie" , "Betsy", "Blue", "Buttercup", "Sue"};

pair<string, string> px[10];

int main()
{
    ifstream cin("lineup.in");
    ofstream cout("lineup.out");

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> px[i].first;
        for(int j = 1; j <= 5; j++)
            cin >> px[i].second;
    }

    do{
        bool ok = 1;
        // map each cow to its position in the permutation
        map<string, int> pos;
        for(int j = 0; j <= 7; j++)
            pos[cows[j]] = j;
        for(int i = 1; i <= n; i++)
        {
            int a = pos[px[i].first];
            int b = pos[px[i].second];
            if(abs(a-b) != 1) // if two cows are not close enough, we need to try another permutation
                ok = 0;
        }
        if(ok)
        {
            for(int j = 0; j <= 7; j++)
                cout << cows[j] << '\n';
            break;
        }
    }while(next_permutation(cows, cows + 8));
    return 0;
}

from itertools import permutations

with open("lineup.in", "r") as fin:
    n = int(fin.readline().strip())
    constraints = []
    for _ in range(n):
        tokens = fin.readline().split()
        constraints.append((tokens[0], tokens[5]))
cows = ["Beatrice", "Belinda", "Bella", "Bessie", "Betsy", "Blue", "Buttercup", "Sue"]
for perm in permutations(cows):
    pos = {cow: i for i, cow in enumerate(perm)}
    ok = True
    for a, b in constraints:
        if abs(pos[a] - pos[b]) != 1:
            ok = False
            break
    if ok:
        with open("lineup.out", "w") as fout:
            for cow in perm:
                fout.write(cow + "\n")
        break