USACO Silver 2015 December - High Card Wins

Authors: Óscar Garries, Ryan Chou

Appears In

Silver - Greedy Algorithms with Sorting

Intuitively, we always want Bessie to win with the smallest card possible. We can ensure this minimum by storing the available cards for both Bessie and Elsie. If Elsie's current card is higher than Bessie's, we can move to the Bessie's next higher card.

You can see the algorithm in action with the test set below:

Implementation

Time Complexity: $\mathcal{O}(N)$

C++

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int MAX_CARDS = 1e5;
bool elsieHas[MAX_CARDS + 1];

Python

import sys

sys.stdin = open("highcard.in", "r")
sys.stdout = open("highcard.out", "w")

elsie_has = set()
n = int(input())

for i in range(n):
	elsie_has.add(int(input()))

Java

// Code from Official USACO Editorial:
import java.io.*;
import java.util.*;

public class HighCard {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("highcard.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("highcard.out")));
		int n = Integer.parseInt(br.readLine());

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