USACO Bronze 2019 December - Cow Gymnastics

Authors: Krish Thawani, Hua Zhi Vee, Jonathan Paulson, Ben Dodge, David Li

Edit This Page

Official Solution

Official Analysis

Video Solution

By David Li

Video Solution Code

Implementation

C++

#include <fstream>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


template <typename T> int index(const vector<T> &vec, const T &n) {
	for (int i = 0; i < vec.size(); i++) {

Java

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


public class Gymnastics {
	public static void main(String[] args) throws IOException {
		BufferedReader read =
		    new BufferedReader(new FileReader("gymnastics.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int sessionNum = Integer.parseInt(initial.nextToken());
		int cowNum = Integer.parseInt(initial.nextToken());

Python

with open("gymnastics.in") as read:
	session_num, cow_num = [int(i) for i in read.readline().split()]
	sessions = []
	for _ in range(session_num):
		sessions.append([int(c) - 1 for c in read.readline().split()])


better_pairs = 0
for c1 in range(cow_num):
	for c2 in range(cow_num):
		if c1 == c2:

Alternate Solution

We generate the ranking as we read the data.

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

Then we iterate though all pairs in O(N2)\mathcal{O}(N^2) time and check if they satisfy the condition. At least one of b[A][B]b[A][B] and b[B][A]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 count\texttt{count} by 1. This is because if both are true, then the pair switches ranking order at some point and is not valid. If only one is true, then the pair maintained a consistent order.

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

Implementation

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

C++

#include <fstream>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {
	std::ifstream read("gymnastics.in");

Java

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


public class Gymnastics {
	public static void main(String[] args) throws IOException {
		BufferedReader read =
		    new BufferedReader(new FileReader("gymnastics.in"));


		StringTokenizer initial = new StringTokenizer(read.readLine());
		int sessionNum = Integer.parseInt(initial.nextToken());

Python

with open("gymnastics.in") as read:
	session_num, cow_num = [int(i) for i in read.readline().split()]
	"""
	better[c1][c2] = True
	if c1 was better than c2 in *any* session (0-indexed).
	"""
	better = [[False for _ in range(cow_num)] for _ in range(cow_num)]
	for _ in range(session_num):
		session = [int(c) - 1 for c in read.readline().split()]
		for i in range(len(session)):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum