USACO 2020 December · Bronze · all three problems

← Full December 2020 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec20results. Each problem heading links to the canonical statement on usaco.org. Code is my own reference C++ — cross-check the official editorial before trusting it under contest pressure.

Problem 1 — Do You Know Your ABCs?

Statement

Farmer John has three positive integers A ≤ B ≤ C. He writes down all seven non-empty subset sums of {A, B, C}: A, B, C, A+B, A+C, B+C, A+B+C, in some order. You are given those seven numbers. Reconstruct A, B, C.

Constraints

Exactly 7 input integers.
1 ≤ each value ≤ 10⁹.
A unique valid (A, B, C) is guaranteed.
Time limit: 2s.

Key idea

Sort the seven sums ascending. The smallest is A, the second-smallest is B (because B ≤ A+B ≤ C is not forced, but B ≤ C and B ≤ A+B). The largest is A+B+C, so C = total − A − B. Then verify the multiset of all seven subset sums matches the input — if any check fails, swap to try (A, B, C) variants where A+B might be smaller than C.

Complexity target

O(1): seven sorts and a constant number of comparisons.

Reference solution (C++)

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

int main() {
    vector<long long> v(7);
    for (auto& x : v) cin >> x;
    sort(v.begin(), v.end());
    // v[0] = A, v[6] = A+B+C. B is the next smallest "atom"; it is either
    // v[1] (if B <= A+B which is always true and B <= C), so v[1] = B.
    long long A = v[0], total = v[6], B = v[1], C = total - A - B;

    // Sanity check: regenerate all 7 sums and compare as a multiset.
    auto gen = [&](long long a, long long b, long long c) {
        vector<long long> s = {a, b, c, a+b, a+c, b+c, a+b+c};
        sort(s.begin(), s.end());
        return s;
    };
    if (gen(A, B, C) != v) {
        // Fallback: B might actually be v[2] if v[1] coincided with A+B-like
        // collision; brute-search C among remaining.
        for (int i = 1; i < 7 && gen(A, v[i], total - A - v[i]) != v; ++i)
            B = v[i + 1];
        B = -1;
        for (int i = 1; i < 6; ++i) {
            long long b = v[i], c = total - A - b;
            if (gen(A, b, c) == v) { B = b; C = c; break; }
        }
    }
    cout << A << " " << B << " " << C << "\n";
}

Pitfalls

Don't assume v[1] = B without checking. If A is tiny and the pairwise sums are close together, v[1] could equal A+something; the verification step catches it.
Output ordering. Must be A B C in non-decreasing order.
Repeated values are legal (e.g., A = B). Multiset equality, not set equality.

Problem 2 — Daisy Chains

Statement

There are N flowers in a line with petal counts p_i. Count the number of contiguous subarrays [l, r] such that the average of p_l..r equals at least one element inside the subarray. Equivalently, count pairs (l, r) where sum(p_l..r) is divisible by (r − l + 1) and the resulting integer average appears in the subarray.

Constraints

1 ≤ N ≤ 1000.
1 ≤ p_i ≤ 1000.
Time limit: 2s.

Key idea

N ≤ 1000 means O(N²) enumeration of (l, r) is only 10⁶. For each (l, r) maintain the running sum and the running max as you extend r. The candidate average is sum / (r − l + 1) only if the division is exact. Then check if any element in [l, r] equals it — maintain a small frequency table or scan, since a single inner scan per (l, r) would be O(N³) = 10⁹; instead, while extending r, also track min and max so you can skip ranges where the average lies outside [min, max], and lazily verify with a frequency array reset per l.

Complexity target

O(N²) with O(1) per (l, r) using a per-l frequency map updated as r advances.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<int> p(N);
    for (auto& x : p) cin >> x;

    long long ans = 0;
    // Per starting l, sweep r and maintain a frequency map of values seen.
    vector<int> cnt(1001, 0);
    for (int l = 0; l < N; ++l) {
        long long sum = 0;
        fill(cnt.begin(), cnt.end(), 0);
        for (int r = l; r < N; ++r) {
            sum += p[r];
            cnt[p[r]]++;
            int len = r - l + 1;
            if (sum % len == 0) {
                int avg = (int)(sum / len);
                if (avg >= 1 && avg <= 1000 && cnt[avg] > 0) ans++;
            }
        }
    }
    cout << ans << "\n";
}

Pitfalls

Average must be integer. Reject (l, r) where (r − l + 1) doesn't divide the sum.
Length-1 subarrays count. Each single element trivially has average equal to itself, contributing N to the answer.
Reset the frequency table per l. Otherwise old data leaks across.
Values bounded by 1000. A fixed-size frequency array is faster than unordered_map.

Problem 3 — Stuck in a Rut

Statement

N cows walk on an infinite 2-D grid. Each cow starts at a distinct point and walks either North (N) or East (E) forever at unit speed. When two cows would meet at the same grid cell at the same time, the one that arrived second stops permanently, while the first continues. In the Bronze version, N is small; output the total distance each cow walks before being stopped (or "Infinity" if it never stops).

Constraints

1 ≤ N ≤ 50 (Bronze).
Coordinates up to 10⁹.
Time limit: 2s.

Key idea

Only an East-walker and a North-walker can collide, and only at the intersection of the East-walker's row y = y_E and the North-walker's column x = x_N, which requires x_E < x_N and y_N < y_E. The arrival times are (x_N − x_E) and (y_E − y_N). The cow with the larger arrival time stops at the intersection. With N ≤ 50, simulate by repeatedly finding the earliest pending collision among not-yet-stopped cows, applying it, and continuing until no collisions remain.

Complexity target

O(N³) collision sweep — trivial at N ≤ 50.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<ll> x(N), y(N);
    vector<char> dir(N);
    for (int i = 0; i < N; ++i) cin >> dir[i] >> x[i] >> y[i];

    vector<ll> dist(N, -1);     // -1 = infinity
    vector<char> stopped(N, 0);

    // Iteratively resolve collisions in time order.
    while (true) {
        int bi = -1, bj = -1; ll bt = LLONG_MAX;
        for (int i = 0; i < N; ++i) if (!stopped[i] && dir[i] == 'E')
            for (int j = 0; j < N; ++j) if (!stopped[j] && dir[j] == 'N') {
                if (x[i] < x[j] && y[j] < y[i]) {
                    ll tE = x[j] - x[i], tN = y[i] - y[j];
                    if (tE == tN) continue;   // simultaneous: neither stops (per rules) [verify]
                    ll tmax = max(tE, tN);
                    if (tmax < bt) { bt = tmax; bi = i; bj = j; }
                }
            }
        if (bi == -1) break;
        ll tE = x[bj] - x[bi], tN = y[bi] - y[bj];
        if (tE > tN) { stopped[bi] = 1; dist[bi] = tE; }
        else         { stopped[bj] = 1; dist[bj] = tN; }
    }
    for (int i = 0; i < N; ++i) {
        if (dist[i] < 0) cout << "Infinity\n";
        else cout << dist[i] << "\n";
    }
}

Pitfalls

Distances, not coordinates. Each cow's reported number is how far it walked, not where it ended up.
Process events in time order. A later collision can be cancelled if one of the cows has already been stopped by an earlier collision.
Tie at the intersection. If both arrive simultaneously, neither stops per the official statement.
"Infinity" output must match the judge's exact spelling.

What Bronze December 2020 was actually testing

P1 — multiset reconstruction. Sort, take extremes, verify by re-expansion.
P2 — O(N²) brute with frequency table. Recognize that N ≤ 1000 invites the quadratic loop and that values fit in a tiny array.
P3 — event-driven simulation. Cleanly enumerate (E, N) pairs and resolve collisions by earliest time.