U USACO Prep

USACO 2020 February · Bronze · all three problems

← Full February 2020 set · Official results

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

Statement

Farmer John has N fence posts at integer coordinates. Bessie wants to enclose a right triangle whose two legs are parallel to the x and y axes, using three of the posts as vertices. Find the maximum possible area (i.e. ½ · |legx| · |legy|, reported as twice the area to keep it integer).

Constraints

Key idea

A right triangle with axis-aligned legs has a "corner" vertex: the one that touches both legs. Fix the corner C = (xc, yc). The other two vertices must share xc (vertical leg) and yc (horizontal leg) respectively. So enumerate every triple where one post shares x with C and one shares y with C, and take the max of |Δx| · |Δy|. N ≤ 100 makes O(N³) trivially fine.

Complexity target

O(N³) ≤ 106 ops. Even O(N · count_x · count_y) is fine.

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<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    // For each post C, find max |Δx| over posts sharing y_c
    // and max |Δy| over posts sharing x_c. Twice the area = |Δx| · |Δy|.
    ll best = 0;
    for (int c = 0; c < N; ++c) {
        int dx = 0, dy = 0;
        for (int i = 0; i < N; ++i) {
            if (Y[i] == Y[c]) dx = max(dx, abs(X[i] - X[c]));
            if (X[i] == X[c]) dy = max(dy, abs(Y[i] - Y[c]));
        }
        best = max(best, (ll)dx * dy);
    }
    cout << best << "\n";
}

Pitfalls

Problem 2 — Mad Scientist

Statement

Farmer John has two strings A and B of equal length N over {G, H}. In one operation he may pick any contiguous substring of A and reverse it. Find the minimum number of operations needed to make A equal to B (or report it's impossible — but with the {G, H} alphabet it's always possible iff A and B have the same multiset of letters).

Constraints

Key idea

Look at the positions where A and B differ. Each maximal contiguous block of differing positions can be "fixed" by a single reversal — but a single reversal can fix at most one block transition per side, so each maximal block of mismatched positions where A has too many G's (and the mirror block where A has too many H's) cancels with one reversal. Counting maximal mismatched blocks and dividing by 2 (since each reversal fixes a "+G" block and a "−G" block together) gives the answer — equivalently, the number of maximal blocks where A[i] = 'G' but B[i] = 'H'.

Complexity target

O(N): one linear scan counting transitions in the (A,B) mismatch type.

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;
    string A, B; cin >> A >> B;

    // Count maximal blocks of positions where A[i]='G' and B[i]='H'.
    // Every such block pairs up with a "G<-H" block via a single reversal,
    // so the answer is exactly that count.
    int ans = 0;
    bool in_block = false;
    for (int i = 0; i < N; ++i) {
        bool bad = (A[i] == 'G' && B[i] == 'H');
        if (bad && !in_block) ++ans;
        in_block = bad;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Swapity Swap

Statement

N cows stand in a line, labeled 1..N. One "round" consists of: reverse cows in positions [a1, b1], then reverse cows in positions [a2, b2]. The two ranges are fixed. Apply this round K times. Output the final line.

Constraints

Key idea

One round is a fixed permutation π of {1..N}. Applying it K times is πK. Decompose π into cycles; within each cycle of length L the final position is the K-th iterate, i.e. rotate by K mod L. With N ≤ 100, cycles are at most length 100 so this is trivial.

Complexity target

O(N) for the permutation, O(N) for cycle decomposition, total O(N).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; long long K;
    int a1, b1, a2, b2;
    cin >> N >> K >> a1 >> b1 >> a2 >> b2;
    --a1; --b1; --a2; --b2;

    // Build permutation perm[i] = where the cow at position i ENDS UP after one round.
    vector<int> pos(N);
    iota(pos.begin(), pos.end(), 0);
    reverse(pos.begin() + a1, pos.begin() + b1 + 1);
    reverse(pos.begin() + a2, pos.begin() + b2 + 1);
    // Now pos[i] is the original index that lands at position i after one round.

    // After K rounds, position i contains the cow originally at pos^K[i].
    vector<int> ans(N);
    vector<bool> seen(N, false);
    for (int i = 0; i < N; ++i) if (!seen[i]) {
        vector<int> cyc;
        int x = i;
        while (!seen[x]) { seen[x] = true; cyc.push_back(x); x = pos[x]; }
        int L = cyc.size();
        long long step = K % L;
        for (int j = 0; j < L; ++j)
            ans[cyc[j]] = cyc[(j + step) % L] + 1;
    }
    for (int v : ans) cout << v << "\n";
}

Pitfalls

What Bronze February 2020 was actually testing