USACO Gold 2015 December - High Card Low Card (Gold)

Official Analysis (C++)

Explanation

First, let's note that we can consider each half of Elsie's cards independently, and it is fine to rearrange each half in any way (because we just need to match each of Elsie's cards to Bessie's cards).

We can find Bessie's cards by checking the cards Elsie doesn't have from $1$ to $2N$. Since the first half of the game gives wins for the highest card and the second half of the game gives wins for the lowest card, it is optimal for Bessie to use her highest $\frac{N}{2}$ cards for the first half and lowest $\frac{N}{2}$ cards for the second half. Now, we know what cards Bessie and Elsie will play for each half, and we need to find the best strategy for Bessie by greedily matching their cards.

For high card, one strategy is for Bessie to play the highest card only if it is higher than Elsie's card. Otherwise, we should play her lowest card, so that we save the higher cards for the future and not waste a good card. To do this, we sort both of Bessie and Elsie's cards in decreasing order. Then, we iterate all of Elsie's cards and if Bessie's highest unmatched card is higher, we match this and go to the next index. Otherwise, we keep the index here, because we can potentially match this to one of Elsie's next cards.

Another strategy is to sort both lists of cards in increasing order, and for each Elsie card pick the lowest Bessie card that beats this. This can be accomplished using binary search or two pointers.

For both strategies, the second half (low card) just uses the reverse logic.

Implementation

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

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

int number_of_wins(vector<int> &bessie, vector<int> &elsie,
                   function<bool(int, int)> cmp) {
	int n = size(bessie);
	assert(size(bessie) == size(elsie));

	sort(begin(bessie), end(bessie), cmp);
	sort(begin(elsie), end(elsie), cmp);

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

public class HighCardGold {
	static boolean[] C;
	static List<Integer> B = new ArrayList<>();
	static List<Integer> F = new ArrayList<>();
	static List<Integer> S = new ArrayList<>();
	static int N;
	public static void main(String[] args) throws IOException {

Copy
with open("cardgame.in") as read:
	N = int(read.readline())
	elsie = [int(read.readline()) for i in range(N)]
	set_elsie = set(elsie)
	# find bessie's cards
	bessie = [i for i in range(1, 2 * N + 1) if i not in set_elsie]

# find the cards they use for both games and sort,
# it's best to use highest cards for first N/2 and lowest for second N/2
elsie_high = sorted(elsie[: N // 2], reverse=True)