U USACO Prep

USACO 2024 December · Bronze · all three problems

← Full December 2024 set · Official results · Focused notes on Problem 1

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

Statement

Bessie rounds a positive integer x to the nearest power of 10 in one step (standard rounding: digit ≥ 5 rounds up). Elsie does chain rounding: she rounds x first to the nearest 10, then that result to the nearest 100, and so on, all the way up to the smallest power of 10 that exceeds x. For each test case N, count the integers 2 ≤ x ≤ N for which the two procedures disagree.

Constraints

Key idea

Chain rounding "ratchets up": an x like 45 rounds to 50, then 50 chains to 100. Bessie's one-step rounding on 45 gives 0 (since 45 < 50 when rounding to 100). Whenever a chain-step pushes a number just over a halfway threshold and that propagates upward, the answers diverge. Enumerate divergent "bad" patterns directly: count numbers whose decimal form has a leading digit 4 followed by a digit ≥ 5 — every such number is a divergence root; multiplying by powers of 10 generates the rest.

Complexity target

O(log10 N) per test case after a tiny precomputation — well under 2s for T = 105.

Reference solution (C++)

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

// Count x in [1, N] whose decimal digits start with the pattern 4d...
// where d >= 5, then any tail. Such x cause chain-rounding to "ratchet"
// up past the 5*10^k boundary while one-shot rounding stays below it.
ll countBad(ll N) {
    ll ans = 0;
    // For each pivot power 10^k (k >= 1), count integers in [4*10^k + 5*10^{k-1}, 5*10^k - 1]
    // and all their decimal-shifted multiples.
    for (ll p = 10; p <= N; p *= 10) {
        ll lo = 4 * p + p / 2;        // e.g. p=10  -> 45
        ll hi = 5 * p - 1;            // e.g. p=10  -> 49
        if (lo > N) break;
        ans += min(N, hi) - lo + 1;
        if (p > N / 10) break;        // overflow guard
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        ll N; cin >> N;
        cout << countBad(N) << "\n";
    }
}

Pitfalls

Problem 2 — Farmer John's Cheese Block

Statement

Farmer John starts with a solid N×N×N cube of cheese. Q operations each remove one 1×1×1 unit cube at a given (x,y,z). After each removal, report how many distinct positions inside the cube can hold a straight 1×1×N "brick" — i.e. a full row, column, or pillar of N consecutive removed unit cubes aligned with one of the three axes.

Constraints

Key idea

There are exactly 3·N² candidate brick positions (one per axis-aligned line through the cube). For each line, keep a counter of how many unit cubes along it have been removed. A line is "full" when the counter hits N. Each carve increments exactly three line-counters (the X-line, Y-line, Z-line through that cell). Maintain the answer incrementally: when a counter goes from N−1 to N, +1; never decrement (carves don't un-remove).

Complexity target

O(1) per query, O(N² + Q) total. Memory 3·N² ≈ 3·106 ints.

Reference solution (C++)

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

int N, Q;

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

    // cntX[y][z] = removed cubes along the x-line at (y,z); similarly for Y, Z.
    vector<vector<int>> cntX(N, vector<int>(N, 0));
    vector<vector<int>> cntY(N, vector<int>(N, 0));
    vector<vector<int>> cntZ(N, vector<int>(N, 0));
    // mark which cells have already been carved, to ignore duplicates [verify]
    // (statement: each carve targets a still-solid cell, so we can skip the set)
    long long fullLines = 0;

    while (Q--) {
        int x, y, z; cin >> x >> y >> z;
        // 0-indexed inside [0, N)
        if (++cntX[y][z] == N) ++fullLines;
        if (++cntY[x][z] == N) ++fullLines;
        if (++cntZ[x][y] == N) ++fullLines;
        cout << fullLines << "\n";
    }
}

Pitfalls

Problem 3 — It's Mooin' Time

Statement

Farmer John has a string s of length N over a small alphabet. A "moo" is a length-3 pattern of the form a-b-b (first character different from the next two, which are equal). Bessie tells him exactly one character of the string may have been corrupted (changed to any other letter). For each candidate pattern (a,b), count how many occurrences appear in s; report every (a,b) whose occurrence count, if we are allowed to repair one bad character, can reach at least F.

Constraints

Key idea

There are only 26·25 = 650 possible (a,b) moo patterns. For each, scan s once and count exact-match triples. Then for each pattern, also check whether flipping one single character (any of N positions to any of 25 alternatives) can push the count to ≥ F: the gain from flipping s[i] is the number of new pattern-matches that include position i minus the matches it destroys. Take the max over i and over target characters. With 650 patterns × N positions × 25 letters this is about 3·108, borderline; tighten by only considering positions adjacent to a "near-miss" triple.

Complexity target

About O(26² · N) ≈ 1.4×107 with the tight enumeration; under 2s comfortably.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, F; cin >> N >> F;
    string s; cin >> s;

    auto countExact = [&](char a, char b) {
        int c = 0;
        for (int i = 0; i + 2 < N; ++i)
            if (s[i] == a && s[i+1] == b && s[i+2] == b) ++c;
        return c;
    };

    auto bestWithOneFlip = [&](char a, char b) {
        int base = countExact(a, b);
        int best = base;
        // Try flipping each position to every possible char, compute delta locally.
        for (int i = 0; i < N; ++i) {
            char orig = s[i];
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == orig) continue;
                s[i] = c;
                int lo = max(0, i - 2), hi = min(N - 3, i);
                int delta = 0;
                for (int j = lo; j <= hi; ++j) {
                    bool nowMatch = (s[j]==a && s[j+1]==b && s[j+2]==b);
                    s[i] = orig;
                    bool wasMatch = (s[j]==a && s[j+1]==b && s[j+2]==b);
                    s[i] = c;
                    delta += (int)nowMatch - (int)wasMatch;
                }
                best = max(best, base + delta);
                s[i] = orig;
            }
        }
        return best;
    };

    vector<pair<char,char>> good;
    for (char a = 'a'; a <= 'z'; ++a)
        for (char b = 'a'; b <= 'z'; ++b) {
            if (a == b) continue;
            if (bestWithOneFlip(a, b) >= F) good.push_back({a, b});
        }

    cout << good.size() << "\n";
    for (auto [a, b] : good) cout << a << b << "\n"; // [verify output format against PDF]
}

Pitfalls

What Bronze December 2024 was actually testing