U USACO Prep

USACO 2020 February · Silver · 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 — Swapity Swapity Swap

Statement

The Silver upgrade of the Bronze shuffle. N cows in a line, M fixed range-reversal operations form one "round"; apply K rounds and output the final line. (Bronze had M = 2 and N = 100; Silver scales both.)

Constraints

Key idea

Same as Bronze: build the permutation π for one round in O(N · M) by applying the M reversals to the identity, then cycle-decompose. Within each cycle of length L, every element advances by K mod L steps. Total work O(N · M + N).

Complexity target

O(N · M) to build π, O(N) to decompose. 107 ops — fast.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; long long K;
    cin >> N >> M >> K;

    vector<int> pos(N);
    iota(pos.begin(), pos.end(), 0);
    for (int m = 0; m < M; ++m) {
        int a, b; cin >> a >> b; --a; --b;
        reverse(pos.begin() + a, pos.begin() + b + 1);
    }
    // pos[i] = original cow index that ends up at position i after one round.

    vector<int> ans(N);
    vector<char> seen(N, 0);
    for (int i = 0; i < N; ++i) if (!seen[i]) {
        vector<int> cyc;
        int x = i;
        while (!seen[x]) { seen[x] = 1; cyc.push_back(x); x = pos[x]; }
        int L = cyc.size();
        long long s = K % L;
        for (int j = 0; j < L; ++j)
            ans[cyc[j]] = cyc[(j + s) % L] + 1;
    }
    for (int v : ans) cout << v << "\n";
}

Pitfalls

Problem 2 — Triangles

Statement

Silver version of Bronze Triangles. Given N fence posts at integer coordinates, compute the sum of (2·area) over every right triangle with axis-aligned legs whose three vertices are posts. Output modulo 109 + 7.

Constraints

Key idea

Fix corner C. Its contribution is (sum of |Δx| over same-y posts) · (sum of |Δy| over same-x posts). Group posts by y-coordinate and by x-coordinate. For each y-group, sort by x and precompute, for every post, the sum of |x − xi| over the group (prefix-sum trick: each x contributes (k·x − prefixSum) on the left and (suffixSum − (m−k)·x) on the right). Same for x-groups. Multiply and sum.

Complexity target

O(N log N) — dominated by sorting within groups.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1'000'000'007;

// For a sorted vector v, return, for each i, the sum of |v[i] - v[j]| over j.
vector<ll> absSumPerIndex(vector<ll> v) {
    int n = v.size();
    sort(v.begin(), v.end());
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + v[i];
    vector<ll> out(n);
    for (int i = 0; i < n; ++i)
        out[i] = (ll)i * v[i] - pref[i] + (pref[n] - pref[i + 1]) - (ll)(n - 1 - i) * v[i];
    return out;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    // For each post, sumDx[i] = sum |X[i]-X[j]| over j sharing Y; sumDy similarly.
    map<ll, vector<int>> byY, byX;
    for (int i = 0; i < N; ++i) { byY[Y[i]].push_back(i); byX[X[i]].push_back(i); }

    vector<ll> sumDx(N, 0), sumDy(N, 0);
    for (auto& [y, idx] : byY) {
        vector<ll> xs; for (int i : idx) xs.push_back(X[i]);
        // We need result aligned to idx order — sort idx by X too.
        vector<int> ord = idx;
        sort(ord.begin(), ord.end(), [&](int a, int b){ return X[a] < X[b]; });
        vector<ll> xs2; for (int i : ord) xs2.push_back(X[i]);
        auto res = absSumPerIndex(xs2);
        for (int k = 0; k < (int)ord.size(); ++k) sumDx[ord[k]] = res[k];
    }
    for (auto& [x, idx] : byX) {
        vector<int> ord = idx;
        sort(ord.begin(), ord.end(), [&](int a, int b){ return Y[a] < Y[b]; });
        vector<ll> ys2; for (int i : ord) ys2.push_back(Y[i]);
        auto res = absSumPerIndex(ys2);
        for (int k = 0; k < (int)ord.size(); ++k) sumDy[ord[k]] = res[k];
    }
    ll ans = 0;
    for (int i = 0; i < N; ++i)
        ans = (ans + sumDx[i] % MOD * (sumDy[i] % MOD)) % MOD;
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Clock Tree

Statement

A tree of N rooms; each room has a clock displaying a value in {0, 1, ..., 11}. From room u Bessie can walk to a neighbor v and the act of arriving in v advances v's clock by +1 mod 12 (the room she came from is unchanged). Pick a starting room and a walk; count the number of starting rooms from which some walk makes every clock show 12 (i.e. 0).

Constraints

Key idea

2-color the tree (it's bipartite — any tree is). Let S0, S1 be the sum of clock values on the two color classes, both mod 12. Each step from u (color c) to v (color 1−c) increments S1−c by 1. So after a walk starting at color c with total k steps, Sc is unchanged and S1−c grew by k. We need both sums to become 0 mod 12. So starting at color c works iff Sc ≡ 0 (mod 12) (or S1−c − Sc ≡ 0 is achievable by choosing k). The clean characterization: starting at color c is valid iff (Sc − S1−c) mod 12 ∈ {0, 1} (one extra step from the start side allowed). Count nodes on the qualifying sides.

Complexity target

O(N) — one BFS/DFS to 2-color, two mod-12 sums.

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<vector<int>> g(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        g[u].push_back(v); g[v].push_back(u);
    }
    // 2-color the tree.
    vector<int> color(N, -1);
    color[0] = 0;
    queue<int> q; q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (color[v] < 0) { color[v] = 1 - color[u]; q.push(v); }
    }
    int S[2] = {0, 0};
    for (int i = 0; i < N; ++i) S[color[i]] = (S[color[i]] + a[i]) % 12;

    // Starting at color c, the walk increments S[1-c] by k (k = walk length).
    // Need S[c] ≡ 0 and S[1-c] + k ≡ 0. k free ≥ 0, so we just need S[c] ≡ 0.
    // But the walk must START somewhere — that first node's clock isn't bumped.
    // The known result: count of valid starts = (S[0]==0 ? count0 : 0) + (S[1]==0 ? count1 : 0)
    // with the small correction that S[c]-S[1-c] can be 0 or +1 mod 12.
    int cnt[2] = {0, 0};
    for (int c : color) cnt[c]++;
    int ans = 0;
    int d = ((S[0] - S[1]) % 12 + 12) % 12;
    if (d == 0) ans += cnt[0] + cnt[1];          // start either side works
    else if (d == 1) ans += cnt[1];              // start on side 1 (bumps side 0 by k, need k ≡ -S[0])
    else if (d == 11) ans += cnt[0];             // symmetric
    // Otherwise no start works.
    cout << ans << "\n";
}

Pitfalls

What Silver February 2020 was actually testing