USACO Bronze 2019 December - Cow Gymnastics

Java

// Created by Krish Thawani

import java.io.*;
import java.util.*;

public class gymnastics {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("gymnastics.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("gymnastics.out"));

C++

Alternate Solution

We generate the ranking as we read the data.

We create a 2D array of booleans which states if $A$ has a ranking higher than $B$ in any point of time. We read every ranking, then for all $\frac{N(N-1)}{2}$ pairs we set $b[A][B]=\text{true}$.

Then we iterate though all pairs in $\mathcal{O}(N^2)$ time and check if they satisfy the condition. At least one of $b[A][B]$ and $b[B][A]$ must be true, and hence we only need to check if they are both true. If one of them is false, we increment our $\texttt{count}$ by 1.

Note that at least one of them must be true, since in every ranking either $A>B$ or $B>A$.

Time Complexity: $\mathcal{O}(K \cdot N^2)$

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

bool b[20][20]; // b[A-1][B-1] = 1 if A was better than B in any session.

int main(){
	ifstream fin("gymnastics.in");
	ofstream fout("gymnastics.out");
	
	int k, n; fin >> k >> n;