USACO 2019 December Contest Bronze Division - Cow Gymnastics

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Just a simple brute force problem. For each pair of cows, we need to check the rankings in every contest and count the number of eligible pairs.

Source codes

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

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

int ranking[22][22];

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

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

    for(int i = 1; i <= k; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            int x;
            cin >> x;
            ranking[i][x] = j;
        }
    }

    int ans = 0;

    for(int i = 1; i <= n; i++)
        for(int j = i+1; j <= n; j++)
        {
            int sa = 0, sb = 0;
            for(int x = 1; x <= k; x++)
            {
                if(ranking[x][i] < ranking[x][j])
                    sa++;
                else
                    sb++;
            }
            if(sa == k || sb == k)
                ans++;
        }

    cout << ans;
    return 0;
}

with open("gymnastics.in", "r") as fin:
    tokens = fin.read().split()
k = int(tokens[0])
n = int(tokens[1])
ranking = [[0]*(n+1) for _ in range(k+1)]
index = 2
for i in range(1, k+1):
    for j in range(1, n+1):
        x = int(tokens[index])
        index += 1
        ranking[i][x] = j
ans = 0
for i in range(1, n+1):
    for j in range(i+1, n+1):
        sa = 0
        sb = 0
        for x in range(1, k+1):
            if ranking[x][i] < ranking[x][j]:
                sa += 1
            else:
                sb += 1
        if sa == k or sb == k:
            ans += 1
with open("gymnastics.out", "w") as fout:
    fout.write(str(ans))