USACO 2018 US Open Contest Bronze Division - Milking Order

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Arrange cows according to the restrictions and see when you can add cow \(1\) by doing some casework and logic.

Source codes

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

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

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> v(n+1), hierarchy(m+1), wh(n+1);
    for(int i = 1; i <= m; i++)
        cin >> hierarchy[i];
    for(int i = 1; i <= k; i++)
    {
        int a, b;
        cin >> a >> b;
        v[b] = a;
        wh[a] = b;
    }

    for(int pos1 = 1; pos1 <= n; pos1++)
    {
        if(v[pos1] != 0)
            continue;
        if(wh[1] != 0 && pos1 != wh[1])
            continue;
        bool ok = 1;
        v[pos1] = 1;
        wh[1] = pos1;
        vector<int> cnt0(n+1);
        for(int j = 1; j <= n; j++)
            if(v[j] == 0)
                cnt0[j] = cnt0[j-1] + 1;
            else
                cnt0[j] = cnt0[j-1];
        int nec = 0;
        int maxipos = 0;
        for(int j = 1; j <= m; j++)
        {
            if(wh[hierarchy[j]] == 0)
                nec++;
            if(wh[hierarchy[j]] != 0 && cnt0[wh[hierarchy[j]]] < nec)
                ok = 0;
            if(wh[hierarchy[j]] != 0 && wh[hierarchy[j]] < maxipos)
                ok = 0;
            if(wh[hierarchy[j]] != 0)
                maxipos = max(maxipos, wh[hierarchy[j]]);
            else
            {
                while(maxipos < n && v[maxipos+1] != 0)
                    maxipos++;
                maxipos++;
            }
        }
        v[pos1] = 0;
        wh[1] = 0;
        if(ok)
        {
            cout << pos1;
            return 0;
        }
    }
    return 0;
}

with open("milkorder.in", "r") as fin:
    tokens = fin.read().split()
it = iter(tokens)
n = int(next(it))
m = int(next(it))
k = int(next(it))

v = [0] * (n + 1)
hierarchy = [0] * (m + 1)
wh = [0] * (n + 1)

for i in range(1, m + 1):
    hierarchy[i] = int(next(it))
for i in range(1, k + 1):
    a = int(next(it))
    b = int(next(it))
    v[b] = a
    wh[a] = b

for pos1 in range(1, n + 1):
    if v[pos1] != 0:
        continue
    if wh[1] != 0 and pos1 != wh[1]:
        continue
    ok = True
    v[pos1] = 1
    wh[1] = pos1
    cnt0 = [0] * (n + 1)
    for j in range(1, n + 1):
        if v[j] == 0:
            cnt0[j] = cnt0[j - 1] + 1
        else:
            cnt0[j] = cnt0[j - 1]
    nec = 0
    maxipos = 0
    for j in range(1, m + 1):
        cow = hierarchy[j]
        if wh[cow] == 0:
            nec += 1
        if wh[cow] != 0 and cnt0[wh[cow]] < nec:
            ok = False
        if wh[cow] != 0 and wh[cow] < maxipos:
            ok = False
        if wh[cow] != 0:
            maxipos = max(maxipos, wh[cow])
        else:
            while maxipos < n and v[maxipos + 1] != 0:
                maxipos += 1
            maxipos += 1
    v[pos1] = 0
    wh[1] = 0
    if ok:
        with open("milkorder.out", "w") as fout:
            fout.write(str(pos1))
        exit(0)