USACO 2017 February Contest Silver Division - Why Did the Cow Cross the Road

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Greedy solution: We sort both cows and chicken and we match the pairs greedily, as we match them in increasing order of the values.

Binary search solution: Similar to the greedy solution, we can find for each cow the smallest chicken which has a larger value than the value of the current cow.

Source code

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

Greedy solution

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

int c, n, ans;
int main() {
    ifstream cin("helpcross.in");
    ofstream cout("helpcross.out");

    cin >> c >> n;
    vector<pair<int, int>> a(n); // cows
    vector<int> b(c);  // chicken
    for (auto& it : b) {
        cin >> it;
    }
    for (auto& it : a) {
        cin >> it.first >> it.second;
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    priority_queue<int> pq;
    int idx = 0;

    for (auto& it : b) {
        while (idx < n && a[idx].first <= it) {
            pq.push(-a[idx++].second);
        }
        while (!pq.empty() && -pq.top() < it) {
            pq.pop();
        }
        if (!pq.empty()) {
            ++ans;
            pq.pop();
        }
    }

    cout << ans << '\n';
    return 0;
}

Binary search solution

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

int c, n;
vector<int> chickens;
vector<pair<int, int>> cows;

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second < b.second;
}

int search(int target) {
    //want to find smallest that is larger than target
    int low = 0;
    int high = c - 1;
    int mid;
    int works = -1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (chickens[mid] >= target) {
            high = mid - 1;
            works = mid;
        }
        else {
            low = mid + 1;
        }
    }
    return works;
}

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

    cin >> c >> n;

    chickens.resize(c);
    cows.resize(n);
    for (int i = 0; i < c; i++) {
        cin >> chickens[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> cows[i].first >> cows[i].second;
    }
    int counter = 0;
    sort(chickens.begin(), chickens.end());
    sort(cows.begin(), cows.end(), compare);
    for (auto i: cows) {
        int a = i.first;
        int b = i.second;
        int temp = search(a);
        if (temp != -1 && chickens[temp] <= b) {
            counter++;
            chickens.erase(chickens.begin() + temp);
            c--;
        }
    }
    cout << counter << '\n';
    return 0;
}