U USACO Prep

USACO 2015 December · Bronze · all three problems

← Full December 2015 set · Official results

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

Statement

Farmer John paints the fence from x=a to x=b. Bessie paints from x=c to x=d. The two intervals may overlap. Output the total length of fence that ends up with paint on it (i.e., the length of the union of [a,b] and [c,d]).

Constraints

Key idea

Union length = (b − a) + (d − c) − overlap, where overlap = max(0, min(b, d) − max(a, c)). With the coordinate range capped at 100 you can also just mark a boolean array of 100 unit-segments and count the true entries, which is more obviously correct under contest pressure.

Complexity target

O(1) arithmetic, or O(100) brute mark — both trivial.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    // Mark each unit segment [i, i+1) for i in [0, 100).
    bool painted[100] = {false};
    for (int i = a; i < b; ++i) painted[i] = true;
    for (int i = c; i < d; ++i) painted[i] = true;

    int total = 0;
    for (int i = 0; i < 100; ++i) if (painted[i]) ++total;
    cout << total << "\n";
}

Pitfalls

Problem 2 — Speeding Ticket

Statement

A road of exactly 100 miles is divided into N consecutive segments, each with a length and a posted speed limit. Bessie drives the full 100 miles, broken into M consecutive segments each with a length and her actual speed. Output the maximum amount, over all positions along the road, by which her actual speed exceeds the posted limit (0 if she never speeds).

Constraints

Key idea

Expand both segmentations into per-mile arrays of length 100: limit[i] for mile i from the road's segmentation, speed[i] for mile i from Bessie's segmentation. Then the answer is maxi(speed[i] − limit[i], 0). With only 100 miles the unrolling is free.

Complexity target

O(100) — both expansion and scan.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;

    int limit[100] = {0}, speed[100] = {0};
    int pos = 0;
    for (int i = 0; i < N; ++i) {
        int len, lim; cin >> len >> lim;
        for (int k = 0; k < len; ++k) limit[pos++] = lim;
    }
    pos = 0;
    for (int i = 0; i < M; ++i) {
        int len, sp; cin >> len >> sp;
        for (int k = 0; k < len; ++k) speed[pos++] = sp;
    }
    int ans = 0;
    for (int i = 0; i < 100; ++i) ans = max(ans, speed[i] - limit[i]);
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Contaminated Milk

Statement

There are N people and M milk types. You're given D drinking records (person, milk, time) and S sick reports (person, time). Exactly one milk type is contaminated, and it has been contaminated since time 0. A person gets sick at most once. A person can be the cause of "sick" only if they drank the contaminated milk strictly before their sick time. You must report the maximum number of people who could ultimately get sick — namely, over every milk type that is consistent with the sick reports (every sick person drank it before they got sick), the total number of people who drank that milk at any time. Take the maximum.

Constraints

Key idea

For each candidate milk type m: check that every sick person p has at least one drinking record of m with time < sick_time(p). If so, count the number of distinct people who ever drank m at any time — each of them could eventually get sick. Output the maximum such count over all valid m.

Complexity target

O(M · (D + N)) which is trivially small.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, D, S; cin >> N >> M >> D >> S;

    // drink[m] = list of (person, time); drinkers[m] = set of people who ever drank m.
    vector<vector<pair<int,int>>> drink(M + 1);
    vector<set<int>> drinkers(M + 1);
    for (int i = 0; i < D; ++i) {
        int p, m, t; cin >> p >> m >> t;
        drink[m].push_back({p, t});
        drinkers[m].insert(p);
    }
    vector<pair<int,int>> sick(S);  // (person, time)
    for (auto& s : sick) cin >> s.first >> s.second;

    int ans = 0;
    for (int m = 1; m <= M; ++m) {
        bool ok = true;
        for (auto [p, t] : sick) {
            bool found = false;
            for (auto [pp, tt] : drink[m]) if (pp == p && tt < t) { found = true; break; }
            if (!found) { ok = false; break; }
        }
        if (ok) ans = max(ans, (int)drinkers[m].size());
    }
    cout << ans << "\n";
}

Pitfalls

What Bronze December 2015 was actually testing