USACO 2021 February Contest Bronze Division - Year of the Cow

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can trace starting from the first relationship all the way to the last one. In order to implement this, we will use BFS, or alternatively DFS.

Source codes

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

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

string cycle[12] = {"Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse", "Goat", "Monkey", "Rooster", "Dog", "Pig", "Rat"};

struct mch
{
    int a, b, c, d;
}; 
mch v[102];

int diff[102];
bool viz[102];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int cnt = 0;
    map<string, int> mp;
    for(int i = 0; i < n; i++)
    {
        int sgn = 0;
        int wh = 0;
        for(int j = 0; j < 8; j++)
        {
            string s;
            cin >> s;
            if(j == 0)
            {
                if(mp.find(s) == mp.end())
                    ++cnt, mp[s] = cnt;
                v[i].a = mp[s];
            }
            if(j == 7)
            {
                if(mp.find(s) == mp.end())
                    ++cnt, mp[s] = cnt;
                v[i].b = mp[s];
            }
            if(j == 3)
            {
                if(s[0] == 'p')
                    sgn = -1;
                else
                    sgn = 1;
            }
            if(j == 4)
            {
                for(int j = 0; j < 12; j++)
                    if(s == cycle[j])
                        wh = j;
            }
        }
        v[i].c = sgn;
        v[i].d = wh;
    }

    queue<int> q;
    q.push(mp["Bessie"]);
    viz[mp["Bessie"]] = 1;
    while(!q.empty())
    {
        int poz = q.front();
        q.pop();
        for(int j = 0; j < n; j++)
        {
            if(v[j].a == poz)
            {
                if(v[j].c == -1)
                {
                    int delta = diff[poz] + 1;
                    while((delta%12 + 12) % 12 != v[j].d)
                        delta++;
                    if(!viz[v[j].b])
                    {
                        viz[v[j].b] = 1;
                        diff[v[j].b] = delta;
                        q.push(v[j].b);
                    }
                }
                else
                {
                    int delta = diff[poz] - 1;
                    while((delta%12 + 12) % 12 != v[j].d)
                        delta--;
                    if(!viz[v[j].b])
                    {
                        viz[v[j].b] = 1;
                        diff[v[j].b] = delta;
                        q.push(v[j].b);
                    }
                }
            }
            if(v[j].b == poz)
            {
                if(v[j].c == 1)
                {
                    int delta = diff[poz] + 1;
                    while((delta%12 + 12) % 12 != v[j].d)
                        delta++;
                    if(!viz[v[j].a])
                    {
                        viz[v[j].a] = 1;
                        diff[v[j].a] = delta;
                        q.push(v[j].a);
                    }
                }
                else
                {
                    int delta = diff[poz] - 1;
                    while((delta%12 + 12) % 12 != v[j].d)
                        delta--;
                    if(!viz[v[j].a])
                    {
                        viz[v[j].a] = 1;
                        diff[v[j].a] = delta;
                        q.push(v[j].a);
                    }
                }
            }
        }
    }
    cout << abs(diff[mp["Bessie"]] - diff[mp["Elsie"]]) << '\n';
    return 0;
}

import sys
from collections import deque

fin = sys.stdin
fout = sys.stdout

cycle = ["Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse", "Goat", "Monkey", "Rooster", "Dog", "Pig", "Rat"]

n = int(fin.readline().strip())

v = []
mp = {}  
cnt = 0

for i in range(n):
    tokens = fin.readline().split()
    sgn = 0
    wh = 0
    constraint = {}
    for j in range(8):
        token = tokens[j]
        if j == 0:
            if token not in mp:
                cnt += 1
                mp[token] = cnt
            constraint['a'] = mp[token]
        if j == 7:
            if token not in mp:
                cnt += 1
                mp[token] = cnt
            constraint['b'] = mp[token]
        if j == 3:
            sgn = -1 if token[0] == 'p' else 1
        if j == 4:
            for idx in range(12):
                if token == cycle[idx]:
                    wh = idx
                    break
    constraint['c'] = sgn
    constraint['d'] = wh
    v.append(constraint)

diff = [0] * (cnt + 1)
viz = [False] * (cnt + 1)

q = deque()
if "Bessie" not in mp:
    fout.write("0")
    sys.exit(0)
start_id = mp["Bessie"]
viz[start_id] = True
diff[start_id] = 0
q.append(start_id)

while q:
    curr = q.popleft()
    for con in v:
        if con['a'] == curr:
            if con['c'] == -1:
                delta = diff[curr] + 1
                while (delta % 12 + 12) % 12 != con['d']:
                    delta += 1
            else: 
                delta = diff[curr] - 1
                while (delta % 12 + 12) % 12 != con['d']:
                    delta -= 1
            if not viz[con['b']]:
                viz[con['b']] = True
                diff[con['b']] = delta
                q.append(con['b'])
        if con['b'] == curr:
            if con['c'] == 1:
                delta = diff[curr] + 1
                while (delta % 12 + 12) % 12 != con['d']:
                    delta += 1
            else: 
                delta = diff[curr] - 1
                while (delta % 12 + 12) % 12 != con['d']:
                    delta -= 1
            if not viz[con['a']]:
                viz[con['a']] = True
                diff[con['a']] = delta
                q.append(con['a'])

if "Elsie" not in mp:
    answer = 0
else:
    answer = abs(diff[mp["Bessie"]] - diff[mp["Elsie"]])
fout.write(str(answer) + "\n")