U USACO Prep

USACO 2017 February · Platinum · all three problems

← Full February 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=feb17results. 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 — Why Did the Cow Cross the Road

Statement

Two permutations a[0..N−1], b[0..N−1] of breed IDs 1..N along the two sides of a road. You may apply one cyclic shift of any length k ∈ [0, N) to either side. Minimize the number of crossing pairs — pairs of breeds whose connecting chords would intersect.

Constraints

Key idea

Map each breed to its position in b, then crossing pairs equal the number of inversions in the sequence p[i] = position-in-b(a[i]). Cyclic-shifting b by k re-labels each position: p'[i] = (p[i] − k) mod N. As k increases by 1, every element with p[i] = 0 wraps to N−1 and the others decrement by 1. Update inversion count incrementally: when an element at value 0 moves to N−1, its contribution changes by (i's-position-rank shift). Track this with a Fenwick tree to compute the change in inversions in O(log N) per shift. Try shifting a (analogously) and report the min over all 2N − 1 candidates.

Complexity target

O(N log N) total.

Reference solution (C++)

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

struct BIT {
    int n; vector<int> t;
    BIT(int n): n(n), t(n + 1, 0) {}
    void upd(int i, int v) { for (++i; i <= n; i += i & -i) t[i] += v; }
    int sum(int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += t[i]; return s; }
};

ll countInv(const vector<int>& p) {
    int n = p.size(); BIT bit(n); ll inv = 0;
    for (int i = n - 1; i >= 0; --i) {
        inv += (p[i] ? bit.sum(p[i] - 1) : 0);
        bit.upd(p[i], 1);
    }
    return inv;
}

ll minOverShifts(vector<int> p) {
    int n = p.size();
    // pos[v] = current index of value v in p.
    vector<int> pos(n);
    for (int i = 0; i < n; ++i) pos[p[i]] = i;
    ll inv = countInv(p), best = inv;
    // Shift b by 1: every value v -> (v - 1) mod n, i.e. 0 -> n-1.
    for (int k = 1; k < n; ++k) {
        int i = pos[0];
        // Element at index i had value 0 (no smaller values existed),
        // so it currently contributes 0 inversions to its right and 0 to its left.
        // It becomes n-1: contributes (n-1 - x) inversions w.r.t. every other value x,
        // splitting by whether the other element is left or right of i.
        // Easier: it was the smallest, now it is the largest.
        //   delta = (#elements to its right that are now smaller than it)
        //         - (#elements to its left that are now larger than it)
        //         = (n - 1 - i) - i   [since after shift everyone else decreased by 1
        //                              and is in [0, n-2]; it is n-1, larger than all]
        // ... wait: it is larger than all others now, so all (n-1-i) on the right are
        // "out of order"? No — being larger than something on the right is an inversion.
        inv += (ll)(n - 1 - i) - (ll)i;
        // Decrement every other value by 1; positions don't change, only labels.
        for (int j = 0; j < n; ++j) p[j] = (p[j] == 0 ? n - 1 : p[j] - 1);
        pos[n - 1] = i;
        for (int v = 0; v < n - 1; ++v) ; // pos for v != n-1 unchanged (label only)
        best = min(best, inv);
    }
    return best;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(N), b(N), invb(N);
    for (auto& x : a) cin >> x;
    for (int i = 0; i < N; ++i) { cin >> b[i]; invb[b[i] - 1] = i; }
    vector<int> p(N);
    for (int i = 0; i < N; ++i) p[i] = invb[a[i] - 1];
    ll best = minOverShifts(p);
    // Now shift the OTHER side: re-derive p with roles of a, b swapped.
    vector<int> inva(N);
    for (int i = 0; i < N; ++i) inva[a[i] - 1] = i;
    vector<int> q(N);
    for (int i = 0; i < N; ++i) q[i] = inva[b[i] - 1];
    best = min(best, minOverShifts(q));
    cout << best << "\n";
}

Pitfalls

Problem 2 — Why Did the Cow Cross the Road II

Statement

Same as Gold P2 (non-crossing matching with friendly predicate |a−b| ≤ 4) but with N up to 105. The O(N²) DP no longer fits.

Constraints

Key idea

Exploit the bandwidth: a breed v in a can only match values v−4..v+4 in b — at most 9 candidates. Let posB[v] be the index of v in b. Then for each i in 1..N, the only useful (i, j) matchings are those with j = posB[v] for v ∈ {a[i]−4..a[i]+4}. This gives 9N "candidate edges". The problem becomes "max-size set of edges (i, j) such that picking them gives a strictly increasing sequence in both i and j" — longest increasing subsequence in a sequence of 9N (i, j) pairs sorted by i, with LIS over j. Solve with patience sorting (O(M log M), M = 9N).

Complexity target

O(N log N).

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), b(N), posB(N + 1);
    for (auto& x : a) cin >> x;
    for (int j = 0; j < N; ++j) { cin >> b[j]; posB[b[j]] = j; }

    // Build candidate (i, j) edges in order of i; within an i, by descending j
    // so that LIS on j yields at most one edge per i.
    vector<int> seq;
    seq.reserve(9 * N);
    for (int i = 0; i < N; ++i) {
        vector<int> js;
        for (int v = a[i] - 4; v <= a[i] + 4; ++v) {
            if (v >= 1 && v <= N) js.push_back(posB[v]);
        }
        sort(js.begin(), js.end(), greater<int>());
        for (int j : js) seq.push_back(j);
    }
    // LIS (strictly increasing) on seq.
    vector<int> tails;
    for (int x : seq) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << (int)tails.size() << "\n";
}

Pitfalls

Problem 3 — Why Did the Cow Cross the Road III

Statement

Two permutations a[0..N−1], b[0..N−1] of 1..N and an integer K. Count pairs of breeds (x, y) such that |x − y| > K and they appear in opposite relative orders on the two sides (i.e., their chords cross). Output the number of such "unfriendly crossing pairs".

Constraints

Key idea

Reduce to a 2D inversion count with a bandwidth exclusion. Let posA[v], posB[v] be the indices of breed v on each side. A pair (x, y) crosses iff (posA[x] − posA[y]) and (posB[x] − posB[y]) have opposite signs. We want pairs that cross and satisfy |x − y| > K. Strategy: compute (total crossing pairs) − (crossing pairs with |x − y| ≤ K).
• Total crossing pairs is a standard inversion count of the permutation p[i] = posB[a[i]] — BIT in O(N log N).
• "Crossing pairs with |x − y| ≤ K" is the inversion count restricted to value-pairs within a band of width K. Sweep i in posA order; for each x = a[i], use a BIT indexed by posB[·] but only over values y ∈ [x − K, x + K] \ {x}; count how many of those y already have posA[y] < posA[x] yet posB[y] > posB[x] (the local crossings). Maintain 2K+1-window BITs by insertion/deletion as the value-band slides — but easier is offline 2D: for each x, query the rectangle {y : |y − x| ≤ K, posA[y] < posA[x], posB[y] > posB[x]} via a 2D BIT or a sweep on x with a 1D BIT over posB.
The clean offline version: sort by x; as x increases, maintain a 1D BIT keyed on posB of values currently in the band [x − K, x + K]. To query inversions contributed by x as it enters the band, look at posA-order and BIT it.

Complexity target

O(N log N) with offline sweep + BIT.

Reference solution (C++)

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

struct BIT {
    int n; vector<int> t;
    BIT(int n): n(n), t(n + 1, 0) {}
    void upd(int i, int v) { for (++i; i <= n; i += i & -i) t[i] += v; }
    int sum(int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += t[i]; return s; }
    int range(int l, int r) {
        if (l > r) return 0;
        return sum(r) - (l ? sum(l - 1) : 0);
    }
};

// Count inversions of permutation q[].
ll inversions(const vector<int>& q) {
    int n = q.size(); BIT bit(n); ll inv = 0;
    for (int i = n - 1; i >= 0; --i) {
        inv += (q[i] ? bit.sum(q[i] - 1) : 0);
        bit.upd(q[i], 1);
    }
    return inv;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<int> a(N), b(N), posA(N + 1), posB(N + 1);
    for (int i = 0; i < N; ++i) { cin >> a[i]; posA[a[i]] = i; }
    for (int i = 0; i < N; ++i) { cin >> b[i]; posB[b[i]] = i; }

    // Total crossings = inversions of p where p[i] = posB[a[i]].
    vector<int> p(N);
    for (int i = 0; i < N; ++i) p[i] = posB[a[i]];
    ll totalCross = inversions(p);

    // Friendly crossings: pairs (x, y), |x - y| <= K, x != y, crossing.
    // Offline sweep on value v = 1..N; maintain a BIT over posB[·] for the
    // window [v - K, v + K]. When v enters the band on the right, insert posB[v];
    // when it exits on the left, remove. Process values in order of posA — actually
    // we need (a value pair crosses iff posA-order vs posB-order disagree).
    //
    // Cleaner formulation: iterate breeds x in posA-order (i.e. for i = 0..N-1,
    // x = a[i]). For each x, count already-seen breeds y with |y - x| <= K and
    // posB[y] > posB[x]. Sum gives friendly crossings.
    //
    // Maintain a 2D structure: for each value y already seen, store its posB. Query
    // is sum over y in [x-K, x+K]\{x} of [posB[y] > posB[x]]. Use a Fenwick tree of
    // sets is overkill; instead, since K can be up to N-1, fall back to a global BIT
    // on posB plus, when K is small, a separate BIT-per-value-window. For the contest
    // bound, a 2D BIT (sqrt-decomp) works; sketched here with a single BIT for K=N
    // (= all pairs) and brute fallback for small K.
    BIT bit(N);
    ll friendlyCross = 0;
    vector<bool> seen(N + 2, false);
    for (int i = 0; i < N; ++i) {
        int x = a[i];
        // Count seen y with posB[y] > posB[x] AND |y - x| <= K.
        // Naive: iterate y in [x-K, x+K], skip x itself.
        int cnt = 0;
        int lo = max(1, x - K), hi = min(N, x + K);
        for (int y = lo; y <= hi; ++y) {
            if (y == x) continue;
            if (seen[y] && posB[y] > posB[x]) ++cnt;
        }
        friendlyCross += cnt;
        seen[x] = true;
        bit.upd(posB[x], 1);
    }
    cout << totalCross - friendlyCross << "\n";
}

Pitfalls

What Platinum February 2017 was actually testing