USACO 2025 US Open Contest Silver Division - Compatible Pairs

Problem link: TBA

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be approached in numerous ways, but the most simple way of doing it consists of sorting the input and then iterating over the numbers in increasing order, prioritizing the sums equal to \(B\) and then the sums equal to \(A\). Last but not least, you will match the pairs with values equal to \(\frac{A}{2}\) or \(\frac{B}{2}\).

Source code

The source codes in C++ and Python can be seen below. The python source code is based on another code with a slightly different logic, although the idea is the same.

def isLeaf (v): 
    return (A-v in cows) != (B-v in cows)

cows = {}
N, A, B = [int(i) for i in input().split()]
if A == B: 
    B = 10**10
for i in range(N):
    ni, di = [int(i) for i in input().split()] 
    cows [di] = ni

leaves = []
for v in cows:
    if isLeaf (v): 
        leaves.append(v)
pairs = 0
while len(leaves) > 0:
    v = leaves.pop()
    ni = cows.pop(v)
    if A-v in cows: 
        w = A-v
    elif B-v in cows: 
        w = B-v
    else:
        if v*2 == A or v*2 == B: 
            pairs += ni//2 
            continue
    pairs += min(ni, cows[w])
    cows [w] -= min(ni, cows [w]) 
    if isLeaf (w): 
        leaves.append(w)
print(pairs)

Observation

The given C++ source code fails on a test case as mentioned in this blog comment. It got AC in the contest, but I will fix the code later on.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

void solve() {
    int n, a, b;
    cin >> n >> a >> b;

    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        mp[y] = x;
    }

    long long ans = 0;
    for (auto x : mp) {
        int complement = a-x.first;
        int complement2 = b-x.first;

        int vx = x.second;
        if (complement2 < x.first && complement2 >= 0) {
            ans += min(vx, mp[complement2]);
            int pp = min(vx, mp[complement2]);
            vx -= pp;
            mp[complement2] -= pp;
        }
        if (complement < x.first && complement >= 0) {
            ans += min(vx, mp[complement]);
            int pp = min(vx, mp[complement]);
            vx -= pp;
            mp[complement] -= pp;
        }
        mp[x.first] = vx;
    }
    for (auto x : mp) {
        if (x.first * 2 == a || x.first * 2 == b) {
            ans += x.second/2;
        }
    }

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

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;

    while (t--) {
        solve();
    }
    return 0;
}