USACO 2021 US Open Contest Bronze Division - Acowdemia II

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Just simulate the process and do it as long as you still have changes remaining.

Source codes

The source code in C++ can be seen below.

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

int n, m;
string v[102];

int grid[102][102];

map<string, int> mp;

int main()
{
    cin >> m >> n;

    for(int i = 0; i < n; i++)
    {
        cin >> v[i];
        mp[v[i]] = i;
    }

    vector<vector<string> > v2;
    for(int i = 0; i < m; i++)
    {
        vector<string> v;
        for(int j = 0; j < n; j++)
        {
            string x;
            cin >> x;
            v.push_back(x);
        }
        v2.push_back(v);
    }
    bool ok = 1;
    while(ok)
    {
        ok = 0;
        for(auto v : v2)
        {
            for(int j = 0; j < n; j++)
            {
                bool canBeJunior = 0;
                for(int q = j+1; q < n; q++)
                {
                    if(v[q-1] > v[q])
                        canBeJunior = 1;
                    if(canBeJunior && grid[mp[v[j]]][mp[v[q]]] == 0)
                    {
                        grid[mp[v[j]]][mp[v[q]]] = 1;
                        grid[mp[v[q]]][mp[v[j]]] = 2;
                        ok = 1;
                    }   
                }                
            }
        }
    }

    for(int i = 0; i < n; cout << '\n', i++)
        for(int j = 0; j < n; j++)
            if(i == j)
                cout << "B";
            else
                if(grid[i][j] == 0)
                    cout << "?";
                else
                    cout << grid[i][j]-1;
    return 0;
}