2015 Dec Silver Problem 2 High Card Wins

Official Problem Statement

High Card Wins

Problem

"Bessie the cow is playing a card game against her friend Elsie. Both of them are dealt a hand of N cards (2 ≤ N ≤ 50000). Since they are playing "High Card Wins", the player with the highest card in each round wins. If both players play the same card, Bessie wins.

Given the cards that Elsie will play in each round, your job is to determine a sequence of cards for Bessie to play such that she wins as many rounds as possible."

Solution

This problem can be solved using a simple greedy algorithm.

Firstly, sort the cards of both Bessie and Elsie. Then, iterate through the sorted lists of cards.

In each round, Bessie should play the smallest card that can beat the card Elsie plays. If Bessie does not have a card that can beat Elsie's card, Bessie should play her smallest card.

This is done by maintaining two pointers, one for Bessie's cards and one for Elsie's cards. In each round, if Bessie has a card that can beat Elsie's card, Bessie plays that card and both pointers move one step. If Bessie does not have such a card, she plays her smallest card and only her pointer moves one step.

The reason why this strategy works is because it tries to make Bessie's higher cards available for future rounds, where they may be more necessary.

Finally, the number of rounds Bessie wins is the number of cards she has successfully played that can beat Elsie's card.

The time complexity of this solution is O(N log N) due to sorting.

Code

C++

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

using namespace std;

int main() {
    ifstream fin("highcard.in");
    ofstream fout("highcard.out");

    int n;
    fin >> n;

    vector<bool> elsieOwns(2*n+1, false);
    for (int i = 0; i < n; i++) {
        int card;
        fin >> card;
        elsieOwns[card] = true;
    }

    deque<int> bessie, elsie;
    for (int i = 1; i <= 2*n; i++) {
        if (elsieOwns[i]) {
            elsie.push_back(i);
        } else {
            bessie.push_back(i);
        }
    }

    int points = 0;
    while (!bessie.empty() && !elsie.empty()) {
        if (bessie.front() > elsie.front()) {
            points++;
            elsie.pop_front();
        }
        bessie.pop_front();
    }

    fout << points << endl;

    return 0;
}

Java

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());
        boolean[] elsieOwns = new boolean[2*n+1];

        for(int i = 0; i < n; i++) {
            elsieOwns[Integer.parseInt(br.readLine())] = true;
        }

        LinkedList<Integer> bessie = new LinkedList<>();
        LinkedList<Integer> elsie = new LinkedList<>();
        int points = 0;
        
        // Loop over the values in increasing order, 
        // the two lists will be in sorted order
        for(int i = 1; i <= 2*n; i++) {
            if(elsieOwns[i]) {
                elsie.add(i);
            } else {
                bessie.add(i);
            }
        }

        // While there are cards in both hands, play the round
        while(!bessie.isEmpty() && !elsie.isEmpty()) {
            // If Bessie's card can beat Elsie's, she plays it
            if(bessie.getFirst() > elsie.getFirst()) {
                points++;
                elsie.removeFirst();
            }
            // Remove the card Bessie just played, whether she wins or loses
            bessie.removeFirst();
        }
        
        pw.println(points);
        pw.close();
    }
}

Python

from collections import deque

def main():
    with open("highcard.in", "r") as fin:
        n = int(fin.readline().strip())
        elsie_own = [False]*(2*n+1)
        for _ in range(n):
            card = int(fin.readline().strip())
            elsie_own[card] = True

    bessie = deque()
    elsie = deque()
    for i in range(1, 2*n+1):
        if elsie_own[i]:
            elsie.append(i)
        else:
            bessie.append(i)

    points = 0
    while bessie and elsie:
        if bessie[0] > elsie[0]:
            points += 1
            elsie.popleft()
        bessie.popleft()

    with open("highcard.out", "w") as fout:
        fout.write(str(points) + '\n')

if __name__ == "__main__":
    main()