USACO 2015 December Contest Silver Division - High Card Wins

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Ideally, we want to be able to defeat Elsie every time using the least effort to do so.

In other words, we want to defeat Elsie whenever she plays a weak card and use the weakest card which is enough to ensure us the victory. Thus, with this idea in mind, we will sort Elsie's cards and Bessie's cards, then add Bessie's cards in a set.

For every card Elsie plays, Bessie will play the smallest card greater than whatever Elsie played and if not possible, we will stop the process and count how many cards Bessie could play while also winning.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    ifstream cin("highcard.in");
    ofstream cout("highcard.out");

    int n;
    cin >> n;

    set<int> s;
    for (int i = 1; i <= n + n; i++) {
        s.insert(i);
    }
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        s.erase(v[i]);
    }
    sort(v.begin() + 1, v.begin() + n + 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (s.lower_bound(v[i]) != s.end()) {
            cnt++;
            s.erase(s.lower_bound(v[i]));
        }
    }
    cout << cnt;
    return 0;
}