Problem Info
Name of problem: High Card Low Card (Gold). 2015 USACO December Contest.
I am getting WA on test cases 9, 10, 11, 13, 14, 15, and the rest of the test cases are producing correct output.
My Work
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <array>
#include <fstream>
#include <cmath>
#include <string>
#include <numeric>
#include <tuple>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>
int main()
{
ifstream fin("data.txt"); // read from file with generated test cases
ll n;
fin >> n;
vector<ll> eHigh; // vector to store elsie cards during "high" portion of game
vector<ll> eLow; // elsies cards during "low" portion of game
vector<ll> bCards; // all of bessies cards
ll input;
bool arr[100100];
for(ll i = 0; i < (n/2); i++) // loop to read in elsies "high" cards
{
fin >> input;
eHigh.push_back(input); // push back input
arr[input] = true; // set arr[input] to true to denote that elsie has that card
}
for(ll i = 0; i < (n/2); i++) // same thing as for "high" cards
{
fin >> input;
eLow.push_back(input);
arr[input] = true;
}
for(ll i = 1; i <= (2*n); i++) // go through all 2n cards
{
if(arr[i] == false) // if elsie doesnt have the card
{
bCards.push_back(i); // bessie has the card
}
}
sort(eHigh.begin(), eHigh.end()); // sort the high cards (elsies) in increasing order
sort(eLow.begin(), eLow.end(), greater<ll>()); // sort the low cards (elsies) in decreasing order
sort(bCards.begin(), bCards.end(), greater<ll>()); // sort bessies cards in decreasing order
sort(bCards.begin(), bCards.begin()+(n/2)); // sort the first n/2 cards (i.e. the highest cards, or the ones that bessie will use during the "high" part of the game) in increasing order
// my strategy is to use the lowest of bessies largest n/2 cards to beat the lowest of elsies "high" cards, and the reverse for the "low" part of the game
ll pos = 0; // position in eHigh array
ll ans = 0; // total number of cards that have been beaten
for(ll i = 0; i < (n/2); i++) // loop through all "high" cards that bessie has
{
if(bCards[i] > eHigh[pos]) // if one of besssies cards is higher than elsies
{
pos++; // increment the position in the elsie array
ans++; // increment the answer
}
}
pos = 0; // reset pos for the eLow vector
for(ll i = (n/2); i < n; i++) // do the same as for the "high" portion but in reverse
{
if(bCards[i] < eLow[pos])
{
pos++;
ans++;
}
}
cout << ans << endl; // print the answer
return 0;
}
The code basically uses a greedy approach (use the lowest possible card/highest possible card during different stages of the game) for both the high card and low card portions of the game and increments the solution according to how many cards can be beaten.
What I’ve Tried
I’ve tried writing a script to generate a bunch of test cases and have manually gone through about 50 test cases for various values of n, and none of them seem to produce any wrong output from my code. I’ve also tried rewriting my code, but that hasn’t worked either. I’ve tried downloading some of the test cases, and my program seems to be producing output that is less than the actual output for the WA test cases.
Please help!! (I’ve been stuck on this problem for a while and am slowlyl osing my sanity)