USACO 2021 US Open Contest Silver Division - Do You Know Your ABCs?

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Brute force problem. We look for every possible sum for \(2\) elements, then we find what would the smallest \(2\) elements be and see if the solution is valid.

Source code

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

#include <iostream>
using namespace std;

set<multiset<int>> sols;
vector<int> v;

void vf(int sum, int b, int c) {
    int a = sum - b - c;
    set<int> s{0, a, b, c, a + b, b + c, c + a, a + b + c};
    for (i = 0; i < v.size(); i++) {
        if (s.count(v[i]) == 0) return;
    }
    sol.insert({a, b, c});
}

void t(int sum) {
    int aux1, aux2;
    set<int> c;
    for (i = 0; i < v.size(); i++) {
        if (v[i] > sum) return;
        if (v[i] > 0 && v[i] != sum) c.insert(min(v[i], sum - v[i]));
    }
    aux1 = *begin(c);
    aux2 = *next(begin(c));
    vf(sum, aux1, aux2);
    vf(sum, aux1, sum - aux2);
}

void solve() {
    int n;
    for (i = 0; i < n; i++) {
        cin >> a;
        v.push_back(a);
    }
    for (i = 0; i < v.size(); i++) {
        for (j = i + 1; j < v.size(); j++) {
            t(v[i] + v[j]);
        }
    }
}

int main() {
    int n;
    cin >> n;
    while (n) {
        solve();
        n--;
    }
    return 0;
}