U USACO Prep

USACO 2017 December · Bronze · all three problems

← Full December 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec17results. 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 — Blocked Billboard

Statement

A rectangular billboard sits on a 2-D plane with corners at (x1, y1) and (x2, y2). A truck, also a rectangle, drives by and may cover part (or all) of the billboard. If the truck completely covers the billboard along some axis-aligned direction, the visible portion of the billboard is the original area minus the overlap. Otherwise the billboard is unobstructed. Output the visible area. (The problem actually gives two billboards and one truck — visible area is each billboard's area minus the truck's overlap with it, summed.)

Constraints

Key idea

For two axis-aligned rectangles A = [ax1, ax2] × [ay1, ay2] and B similar, the overlap rectangle has x-extent [max(ax1, bx1), min(ax2, bx2)] and y-extent analogous. The overlap area is the product of those extents if both are positive, else 0. Visible area of A given truck T = area(A) − area(A ∩ T). Sum over the two billboards.

Complexity target

O(1). The whole problem is a fixed-size arithmetic identity.

Reference solution (C++)

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

struct R { int x1, y1, x2, y2; };

int area(const R& r) { return (r.x2 - r.x1) * (r.y2 - r.y1); }

int overlap(const R& a, const R& b) {
    int xl = max(a.x1, b.x1), xr = min(a.x2, b.x2);
    int yl = max(a.y1, b.y1), yr = min(a.y2, b.y2);
    if (xr <= xl || yr <= yl) return 0;
    return (xr - xl) * (yr - yl);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    R a, b, t;
    cin >> a.x1 >> a.y1 >> a.x2 >> a.y2;
    cin >> b.x1 >> b.y1 >> b.x2 >> b.y2;
    cin >> t.x1 >> t.y1 >> t.x2 >> t.y2;

    int ans = (area(a) - overlap(a, t)) + (area(b) - overlap(b, t));
    cout << ans << "\n";
}

Pitfalls

Problem 2 — The Bovine Shuffle

Statement

N cows stand in positions 1..N. A shuffle is described by a permutation a1..aN: the cow currently at position i moves to position ai. The shuffle is applied three times. Given the final ordering of cows (the IDs at each position after three shuffles), recover and print the original ordering.

Constraints

Key idea

Three forward applications of permutation a correspond to one application of a3. To invert, apply the inverse permutation three times to the final array: for each position i, the cow there came from position a−1(i) one step earlier, and so on. Equivalently, build b where b[a[i]] = final[i], then apply that step three times.

Complexity target

O(N) per shuffle step, three steps total → O(N).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(N + 1), cur(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i];
    for (int i = 1; i <= N; ++i) cin >> cur[i]; // ordering after 3 shuffles

    // Invert the shuffle three times.
    // One forward shuffle: nxt[a[i]] = cur[i].
    // So one backward shuffle: prv[i] = cur[a[i]].
    for (int step = 0; step < 3; ++step) {
        vector<int> prv(N + 1);
        for (int i = 1; i <= N; ++i) prv[i] = cur[a[i]];
        cur = prv;
    }
    for (int i = 1; i <= N; ++i) cout << cur[i] << "\n";
}

Pitfalls

Problem 3 — Milk Measurement

Statement

Farmer John has 3 cows, each starting at 7 gallons/day. Each day in chronological order there is one event: cow c gains or loses some milk. After each event, determine the current set of top-producing cows (those tied for max). Count the number of days the set of top producers changes from the previous day.

Constraints

Key idea

Sort events by day. Maintain a map cow → current production (initial 7). After each event, recompute the set of cows tied for the max. Compare to the previous set; if different, increment the answer. The "previous" before any events is {all three cows, since all tie at 7}.

Complexity target

O(N log N) for sorting; O(1) per event since there are only 3 cows.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<tuple<int,int,int>> ev(N); // day, cow, delta
    for (auto& [d, c, x] : ev) cin >> d >> c >> x;
    sort(ev.begin(), ev.end());

    map<int,int> prod = {{7, 7}, {9, 7}, {11, 7}};
    auto topSet = [&]() {
        int m = INT_MIN;
        for (auto& [k,v] : prod) m = max(m, v);
        set<int> s;
        for (auto& [k,v] : prod) if (v == m) s.insert(k);
        return s;
    };
    auto prevTop = topSet();
    int ans = 0;
    for (auto& [d, c, x] : ev) {
        prod[c] += x;
        auto cur = topSet();
        if (cur != prevTop) { ++ans; prevTop = cur; }
    }
    cout << ans << "\n";
}

Pitfalls

What Bronze December 2017 was actually testing