U USACO Prep

USACO 2018 January · Bronze · all three problems

← Full January 2018 set · Official results

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

Statement

A rectangular billboard is axis-aligned with corners (x1,y1) and (x2,y2). A rectangular truck (also axis-aligned) parks in front of part of it. The truck is guaranteed to cover the billboard along a full side — i.e. the unblocked portion of the billboard, if any, is itself a single axis-aligned rectangle (possibly empty, possibly the entire billboard). Output the area of the visible part of the billboard.

Constraints

Key idea

Intersect the truck with the billboard to get the overlap rectangle (clip on each axis). Because the truck covers a full side of the billboard, the visible portion is itself a rectangle. Concretely: if the overlap spans the full billboard width, shrink vertically; if it spans the full billboard height, shrink horizontally; otherwise (no full-side coverage / no overlap) the visible area is the original billboard area minus the overlap area.

Complexity target

O(1).

Reference solution (C++)

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

int main() {
    // billboard: (bx1, by1) - (bx2, by2)
    // truck:     (tx1, ty1) - (tx2, ty2)
    int bx1, by1, bx2, by2, tx1, ty1, tx2, ty2;
    cin >> bx1 >> by1 >> bx2 >> by2;
    cin >> tx1 >> ty1 >> tx2 >> ty2;

    // Clip truck to billboard.
    int ox1 = max(bx1, tx1), oy1 = max(by1, ty1);
    int ox2 = min(bx2, tx2), oy2 = min(by2, ty2);

    long long billboard = (long long)(bx2 - bx1) * (by2 - by1);

    if (ox1 >= ox2 || oy1 >= oy2) {
        // No overlap at all.
        cout << billboard << "\n";
        return 0;
    }

    bool fullX = (ox1 == bx1 && ox2 == bx2);  // overlap spans billboard width
    bool fullY = (oy1 == by1 && oy2 == by2);  // overlap spans billboard height

    if (fullX && fullY) { cout << 0 << "\n"; return 0; }
    // Guaranteed: at least one of fullX, fullY holds, so visible region is a rectangle.
    long long covered = (long long)(ox2 - ox1) * (oy2 - oy1);
    cout << billboard - covered << "\n";
}

Pitfalls

Problem 2 — Lifeguards

Statement

N lifeguards each cover a half-open time interval [ai, bi). Farmer John must fire exactly one lifeguard. Output the maximum total amount of time during which at least one of the remaining N−1 lifeguards is on duty.

Constraints

Key idea

N is tiny. For each candidate to fire, compute the union length of the other N−1 intervals by sorting + sweeping, and take the max. The "remove one interval" trick is just brute force at N ≤ 100: O(N²) intervals, O(N log N) per union — well under a second.

Complexity target

O(N² log N), with N ≤ 100 that's ~10⁶ ops.

Reference solution (C++)

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

int N;
vector<pair<int,int>> iv;

ll unionLen(int skip) {
    vector<pair<int,int>> v;
    v.reserve(N);
    for (int i = 0; i < N; ++i) if (i != skip) v.push_back(iv[i]);
    sort(v.begin(), v.end());
    ll total = 0;
    int curL = -1, curR = -1;
    for (auto& p : v) {
        if (p.first > curR) {
            if (curR > curL) total += curR - curL;
            curL = p.first; curR = p.second;
        } else {
            curR = max(curR, p.second);
        }
    }
    if (curR > curL) total += curR - curL;
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    iv.resize(N);
    for (auto& p : iv) cin >> p.first >> p.second;
    ll best = 0;
    for (int i = 0; i < N; ++i) best = max(best, unionLen(i));
    cout << best << "\n";
}

Pitfalls

Problem 3 — Out of Place

Statement

The cows enter the barn in some order with distinct heights h1,…,hN. They want to be sorted in increasing order of height. Bessie can swap any two adjacent cows; one such swap counts as one "swap event". The herd, however, only counts the minimum number of cows whose positions must change for the ordering to become sorted. Output that minimum count, minus 1 (the cows in the herd can re-shuffle among themselves once everyone misplaced has been identified). If the herd is already sorted output 0.

Constraints

Key idea

Compare the input array to its sorted copy. Count the indices i where the values differ — those are the cows that must move. If that count is zero the answer is 0; otherwise the answer is count − 1 (a permutation of k misplaced elements can always be realized with k − 1 swaps because they form cycles whose total swap cost is k − number_of_cycles, and in the worst case the misplaced set is one big cycle).

Complexity target

O(N log 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);
    for (auto& x : a) cin >> x;
    vector<int> s = a;
    sort(s.begin(), s.end());
    int bad = 0;
    for (int i = 0; i < N; ++i) if (a[i] != s[i]) ++bad;
    cout << (bad == 0 ? 0 : bad - 1) << "\n";
}

Pitfalls

What Bronze January 2018 was actually testing