USACO Silver 2017 February - Why Did the Cow Cross the Road I

Authors: Benjamin Qi, Brad Ma, David Guo

Edit This Page

Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

Let’s focus on the chicken with the earliest time preference for helping a cow. If no cow needs to cross the road at that time, we can disregard this chicken. However, if there are cows that need to cross at that time, we have some options for assigning the chicken. Intuitively, we should assign this chicken to the cow whose crossing time window ends the earliest. This approach maximizes flexibility for assigning other chickens to cows later.

Implementation

Time Complexity: O(Nlog⁡N+Clog⁡C)\mathcal O(N \log N+C\log C)

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>


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

Java

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


public class HelpCross {
 	Code Snippet: Cow Class (Click to expand)


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("helpcross");
		int numChickens = io.nextInt();
		int numCows = io.nextInt();

Python

import heapq


with open("helpcross.in") as read:
	num_chickens, num_cows = [int(i) for i in read.readline().split()]


	chickens = [int(read.readline()) for _ in range(num_chickens)]


	cows = []
	for _ in range(num_cows):
		cows.append(tuple(int(i) for i in read.readline().split()))

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