USACO 2016 December · Bronze · all three problems

← Full December 2016 set · Official results

Problem 1 — Square Pasture

Statement

Farmer John has two non-overlapping axis-aligned rectangular pastures, given by their lower-left and upper-right corners. He wants to replace them with one axis-aligned square that fully contains both rectangles. Output the smallest possible area of such a square.

Constraints

• All rectangle coordinates are integers in [0, 10].
• For each rectangle, x₂ > x₁ and y₂ > y₁.
• The two rectangles do not overlap (may or may not touch).
• Time limit: 2s. Memory limit: 256 MB.

Key idea

Compute the bounding box of the two rectangles: xLo = min of both x₁, xHi = max of both x₂, similarly for y. The smallest enclosing square has side s = max(xHi − xLo, yHi − yLo); the answer is s². No geometry tricks are needed because the input range is tiny.

Complexity target

O(1) arithmetic. Coordinates are 0–10, so even brute force over the 11×11 lattice is trivial.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // Each rectangle: x1 y1 x2 y2 (lower-left and upper-right corners).
    int ax1, ay1, ax2, ay2, bx1, by1, bx2, by2;
    cin >> ax1 >> ay1 >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;

    int xLo = min(ax1, bx1), xHi = max(ax2, bx2);
    int yLo = min(ay1, by1), yHi = max(ay2, by2);

    int side = max(xHi - xLo, yHi - yLo);
    cout << side * side << "\n";
}

Pitfalls

• It's an axis-aligned square, not a rectangle. The side must be the larger of the two bounding spans.
• Don't output the side — output the area. Easy to drop the squaring step.
• Coordinates fit in int. No overflow risk.
• Rectangles may share an edge but not overlap. Still works: min/max of corners handles either case.

Problem 2 — Block Game

Statement

Farmer John has N two-sided spelling boards. Each board shows a word on each side. For any board, only one side is visible. The cows need a multiset of letter blocks (each block has one letter on it) such that no matter which side of each board faces up, they can spell every visible word using a subset of their blocks. Find the minimum total number of blocks.

Constraints

• 1 ≤ N ≤ 100.
• Each word has between 1 and 10 lowercase letters.
• Time limit: 2s. Memory limit: 256 MB.

Key idea

For each board the worst case is "whichever side is up, we need enough copies of every letter to spell that word". So for each board and each letter c, the requirement is max(count_front(c), count_back(c)). Sum that per-board worst case across all 26 letters and across all boards — each board is independent because boards never need to be spelled simultaneously.

Complexity target

O(N · L) where L is total word length. Trivial.

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;

    // Per-letter answer = max over boards of max(front_cnt, back_cnt).
    int need[26] = {0};
    for (int i = 0; i < N; ++i) {
        string a, b; cin >> a >> b;
        int ca[26] = {0}, cb[26] = {0};
        for (char c : a) ca[c - 'a']++;
        for (char c : b) cb[c - 'a']++;
        for (int j = 0; j < 26; ++j)
            need[j] = max(need[j], max(ca[j], cb[j]));
    }
    int ans = 0;
    for (int j = 0; j < 26; ++j) ans += need[j];
    cout << ans << "\n";
}

Pitfalls

• Boards are not spelled simultaneously. So per letter you take the global max across boards, not the sum.
• Per board, the two sides compete — take the side that needs more of that letter, not the sum of both sides.
• Case sensitivity. Statement uses lowercase letters; index as c - 'a'.
• Multiplicities matter. "moo" needs two o-blocks, not one.

Problem 3 — The Cow-Signal

Statement

Given an M×N grid of characters and a scaling factor K, output the grid scaled up by K in both dimensions: each input cell becomes a K×K block of the same character.

Constraints

• 1 ≤ M, N, K ≤ 10.
• Characters are printable ASCII (no whitespace inside a row).
• Time limit: 2s. Memory limit: 256 MB.

Key idea

For each input row, print K copies of that row, where each character is itself repeated K times. No data structure beyond a string is needed.

Complexity target

O(M · N · K²) output. With all parameters ≤ 10 this is at most 10000 characters.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, N, K; cin >> M >> N >> K;
    vector<string> g(M);
    for (auto& r : g) cin >> r;

    // For each input row, emit K copies; each character expanded to K copies.
    for (int i = 0; i < M; ++i) {
        string expanded;
        expanded.reserve(N * K);
        for (char c : g[i]) expanded.append(K, c);
        for (int rep = 0; rep < K; ++rep) cout << expanded << "\n";
    }
}

Pitfalls

• Input order is M then N (rows then columns). Read carefully — easy to swap.
• Don't use cin with character-by-character; read each row as a string.
• K = 1 is a valid degenerate case. The code handles it without a special branch.
• No trailing blank line. Standard "\n" after each row is sufficient.

What Bronze December 2016 was actually testing

• P1 — bounding boxes. Recognize the answer depends only on the union's xy-span.
• P2 — per-letter independence. Letter counts decompose; per-board take the max of two sides, per-letter take the max across boards.
• P3 — output formatting. Read M and N in the right order; repeat characters and rows by K.