U USACO Prep

USACO 2021 December · Bronze · all three problems

← Full December 2021 set · Official results

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

Statement

Bessie has N cows in a line, each Guernsey (G) or Holstein (H). A "lonely photo" is a contiguous group of at least 3 cows in which exactly one cow's breed appears only once and every other cow shares the other breed. Count the number of lonely photos.

Constraints

Key idea

Each lonely photo has exactly one "loner" cow. Fix the loner at position i with breed b. Let L be the length of the maximal run of the opposite breed ending at i−1 and R the length of the maximal run of the opposite breed starting at i+1. The number of valid intervals [l,r] containing i where the loner is the only b is L·R + (L − 1 + R − 1) provided the resulting length is ≥ 3. Sum over i.

Complexity target

O(N) after a single sweep that computes left/right run lengths of the opposite breed at every i.

Reference solution (C++)

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

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

    // L[i] = length of maximal run of the OPPOSITE breed ending at i-1
    // R[i] = length of maximal run of the OPPOSITE breed starting at i+1
    vector<int> L(N, 0), R(N, 0);
    for (int i = 1; i < N; ++i)
        L[i] = (s[i - 1] != s[i]) ? L[i - 1] + 1 : 0;
    for (int i = N - 2; i >= 0; --i)
        R[i] = (s[i + 1] != s[i]) ? R[i + 1] + 1 : 0;

    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        // Intervals where i is the unique opposite-breed loner, length >= 3.
        // Pick a>=0 cows from left run, b>=0 from right run, with a+b+1>=3
        // i.e., a + b >= 2.
        ll a = L[i], b = R[i];
        ll total = (a + 1) * (b + 1);       // all (a',b') with 0<=a'<=a, 0<=b'<=b
        ll bad = 1 + a + b;                 // those with a'+b' <= 1
        ans += max<ll>(0, total - bad);
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Air Cownditioning

Statement

The barn has N stalls with current temperatures pi and target temperatures qi. In one operation Farmer John picks a contiguous range [l, r] and adds +1 or −1 to every pi in that range. Compute the minimum number of operations to make every stall match its target.

Constraints

Key idea

Let di = qi − pi be the required change. A range +1 raises a contiguous block of d; equivalently it changes the difference array Δi = di − di−1 by +1 at l and −1 at r+1. Each operation moves exactly two units of |Δ| toward zero. The minimum number of operations equals max(Σ positive Δ, Σ |negative Δ|) — and since Σ Δ collapses to dN, this is simply the sum of positive jumps in d (treating d0 = 0). Equivalently: sum of max(0, di − di−1) for i = 1..N.

Complexity target

O(N): one pass to compute differences, one pass to sum positive parts.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> p(N), q(N);
    for (auto& x : p) cin >> x;
    for (auto& x : q) cin >> x;

    // d[i] = required delta at stall i. Treat d[-1] = 0.
    // Each range operation flips a +1/-1 pair in the difference array of d.
    // Minimum ops = sum of positive jumps d[i] - d[i-1].
    ll ans = 0, prev = 0;
    for (int i = 0; i < N; ++i) {
        ll d = q[i] - p[i];
        if (d > prev) ans += d - prev;
        prev = d;
    }
    // Also "close out" the trailing edge — equivalent to the final d -> 0
    // step, which contributes nothing because we only count positive jumps
    // and going to zero is non-positive when prev >= 0.

    cout << ans << "\n";
}

Pitfalls

Problem 3 — Walking Home

Statement

Bessie walks from the top-left of an N×N grid to the bottom-right, taking only steps Down or Right. Some cells are blocked (cannot be entered). She is allowed at most K direction changes (i.e. at most K places along her path where the move type switches from Down to Right or vice versa). Count the number of valid paths.

Constraints

Key idea

DP with state (row, col, last direction, changes used). Transitions move down or right; a change increments the "changes used" counter only when the new direction differs from the previous one. Start state has no previous direction (or two seed states for the first move). Final answer is the sum over states at (N, N) with changes ≤ K.

Complexity target

O(N² · K · 2) states per test, O(1) transitions. With N ≤ 50, K ≤ 3, comfortably fast.

Reference solution (C++)

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

void solve() {
    int N, K; cin >> N >> K;
    vector<string> g(N);
    for (auto& r : g) cin >> r;

    // dp[i][j][k][d] = # paths to (i,j) using exactly k changes,
    // last move direction d (0 = down, 1 = right).
    vector dp(N, vector(N, vector(K + 1, array<ll, 2>{0, 0})));
    // Seed: the first move from (0,0) is either to (1,0) [down] or (0,1) [right],
    // with 0 changes used.
    if (N > 1 && g[1][0] == '.') dp[1][0][0][0] = 1;
    if (N > 1 && g[0][1] == '.') dp[0][1][0][1] = 1;

    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j) {
        if (g[i][j] == 'H') continue;
        for (int k = 0; k <= K; ++k)
          for (int d = 0; d < 2; ++d) if (dp[i][j][k][d]) {
            // Move down -> new direction 0. Change if old direction was 1.
            if (i + 1 < N && g[i + 1][j] == '.') {
                int nk = k + (d == 1 ? 1 : 0);
                if (nk <= K) dp[i + 1][j][nk][0] += dp[i][j][k][d];
            }
            if (j + 1 < N && g[i][j + 1] == '.') {
                int nk = k + (d == 0 ? 1 : 0);
                if (nk <= K) dp[i][j + 1][nk][1] += dp[i][j][k][d];
            }
          }
      }
    ll ans = 0;
    for (int k = 0; k <= K; ++k) for (int d = 0; d < 2; ++d) ans += dp[N - 1][N - 1][k][d];
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}

Pitfalls

What Bronze December 2021 was actually testing