USACO Silver 2015 December - High Card Wins
Authors: Óscar Garries, Ryan Chou
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:
C++
#include <algorithm>#include <cstdio>#include <iostream>#include <vector>using namespace std;const int MAX_CARDS = 1e5;bool elsieHas[MAX_CARDS + 1];
Python
import syssys.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!