U USACO Prep

USACO 2017 February · Gold · 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

Bessie walks from cell (0,0) to cell (N−1, N−1) of an N×N grid of fields. Moving to an adjacent field costs T (the time to cross the road between two fields). She also "stops to eat grass" at every third field she enters, paying grass-time g[r][c]. Output the minimum total time.

Constraints

Key idea

Dijkstra on a state (r, c, k) where k ∈ {0, 1, 2} is "number of moves taken since the last grass snack, mod 3". Moving to a neighbor costs T; if the new k becomes 0 (i.e. it was 2 before the move and now wraps), add g[r'][c']. Start state is (0, 0, 0) — the starting cell does not count as an eat. Answer is min over k of dist(N−1, N−1, k).

Complexity target

O(3 N² log(3 N²)). At N = 100 this is ~3·104 nodes — instant.

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; ll T; cin >> N >> T;
    vector<vector<ll>> g(N, vector<ll>(N));
    for (auto& row : g) for (auto& x : row) cin >> x;

    auto id = [&](int r, int c, int k) { return (r * N + c) * 3 + k; };
    vector<ll> dist(3 * N * N, LLONG_MAX);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[id(0, 0, 0)] = 0; pq.push({0, id(0, 0, 0)});
    int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        int k = u % 3, c = (u / 3) % N, r = (u / 3) / N;
        for (int m = 0; m < 4; ++m) {
            int nr = r + dr[m], nc = c + dc[m];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            int nk = (k + 1) % 3;
            ll nd = d + T + (nk == 0 ? g[nr][nc] : 0);
            int v = id(nr, nc, nk);
            if (nd < dist[v]) { dist[v] = nd; pq.push({nd, v}); }
        }
    }
    ll ans = LLONG_MAX;
    for (int k = 0; k < 3; ++k) ans = min(ans, dist[id(N - 1, N - 1, k)]);
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Why Did the Cow Cross the Road II

Statement

Two sequences a[1..N], b[1..N] each a permutation of 1..N (breed IDs along the two sides of a road). Draw the maximum number of non-crossing crosswalks (a[i] ↔ b[j]) such that the connected breeds are "friendly", i.e. |a[i] − b[j]| ≤ 4, and each field is used at most once.

Constraints

Key idea

"Non-crossing matching" = longest common-friendly subsequence. Standard LCS DP: dp[i][j] = best matching using prefixes a[1..i] and b[1..j]. Transition: dp[i][j] = max(dp[i−1][j], dp[i][j−1], dp[i−1][j−1] + [|a[i]−b[j]|≤4]).

Complexity target

O(N²) time and memory. At N = 1000, 106 ops.

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 + 1), b(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i];
    for (int i = 1; i <= N; ++i) cin >> b[i];

    vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; ++i)
      for (int j = 1; j <= N; ++j) {
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
          if (abs(a[i] - b[j]) <= 4)
              dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
      }
    cout << dp[N][N] << "\n";
}

Pitfalls

Problem 3 — Why Did the Cow Cross the Road III

Statement

2N crossing points are listed in clockwise order around a circle. Each of N cows appears exactly twice (once for entry, once for exit). A pair of cows' chords cross iff exactly one endpoint of one chord lies strictly inside the arc spanned by the other's two endpoints. Count crossing pairs.

Constraints

Key idea

Linearize: cut the circle at position 0 and treat the sequence as positions 0..2N−1. For each cow c let f(c) and s(c) be its first and second occurrences. Two cows i, j cross iff their intervals [f, s] properly interleave: f(i) < f(j) < s(i) < s(j) (or symmetric). Sweep i from left to right; maintain a Fenwick tree indexed by position over "open" cows (those whose first endpoint has been seen but not yet closed). At position p:
• If this is the first occurrence of cow c, mark position p as open in the BIT.
• If this is the second occurrence of cow c (with first at f(c)), the number of crossings with c is the number of open intervals whose first endpoint lies in (f(c), p) — query BIT in that range. Then clear position f(c).

Complexity target

O(N log N).

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) {                // [l, r] inclusive; -1 if empty
        if (l > r) return 0;
        return sum(r) - (l ? sum(l - 1) : 0);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    int M = 2 * N;
    vector<int> first(N + 1, -1);
    BIT bit(M);
    ll ans = 0;
    for (int p = 0; p < M; ++p) {
        int c; cin >> c;
        if (first[c] == -1) {
            first[c] = p;
            bit.upd(p, +1);
        } else {
            // crossings with cow c = open firsts strictly between first[c]+1 and p-1
            ans += bit.range(first[c] + 1, p - 1);
            bit.upd(first[c], -1);            // close cow c
        }
    }
    cout << ans << "\n";
}

Pitfalls

What Gold February 2017 was actually testing