U USACO Prep

USACO 2017 January · Gold · all three problems

← Full January 2017 set · Official results

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

Statement

N cows stand in a line with distinct heights h1..hN. For each cow i, let Li be the number of cows on her left that are strictly taller and Ri the same on her right. Cow i is unbalanced when max(Li, Ri) > 2 · min(Li, Ri). Count the unbalanced cows.

Constraints

Key idea

Coordinate-compress heights to ranks 1..N. Compute Li with a Fenwick tree indexed by rank: sweep left-to-right and at position i, Li = (# inserted so far) − (# of inserted ranks ≤ rank(hi)) = (i) − prefix sum up to rank(hi). Then sweep right-to-left for Ri. Compare max/min with the doubled threshold (use long long).

Complexity target

O(N log N) total — two BIT sweeps plus the rank-compression sort.

Reference solution (C++)

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> h(N);
    for (auto& x : h) cin >> x;

    // Rank-compress: rank[i] in 1..N, larger height -> larger rank.
    vector<int> srt = h;
    sort(srt.begin(), srt.end());
    vector<int> r(N);
    for (int i = 0; i < N; ++i)
        r[i] = int(lower_bound(srt.begin(), srt.end(), h[i]) - srt.begin()) + 1;

    // L[i] = # of taller cows to the left of i.
    vector<int> L(N), R(N);
    BIT bl(N);
    for (int i = 0; i < N; ++i) {
        L[i] = i - bl.qry(r[i]);  // inserted-so-far minus those with rank <= r[i]
        bl.upd(r[i]);
    }
    BIT br(N);
    for (int i = N - 1; i >= 0; --i) {
        R[i] = (N - 1 - i) - br.qry(r[i]);
        br.upd(r[i]);
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        long long a = L[i], b = R[i];
        long long lo = min(a, b), hi = max(a, b);
        if (hi > 2 * lo) ++ans;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Hoof, Paper, Scissors

Statement

Same setup as Silver, but Bessie may switch her gesture at most K times across N rounds (0 ≤ K ≤ 20). Maximize wins given FJ's known sequence.

Constraints

Key idea

DP. State dp[i][k][g] = best wins through the first i rounds with k switches used so far, currently playing gesture g. Transition: at round i+1, either keep g (dp[i+1][k][g] = dp[i][k][g] + win(g, fj[i+1])) or switch to a different g' (dp[i+1][k+1][g'] = dp[i][k][g] + win(g', fj[i+1])). Final answer = max over k ≤ K and g of dp[N][k][g]. Memory: O(N · K · 3); roll on i to save space if needed.

Complexity target

O(N · K · 9) ≈ 10⁵ · 20 · 9 = 1.8 · 10⁷. Comfortable in 2s.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<int> fj(N);
    for (int i = 0; i < N; ++i) {
        char c; cin >> c;
        fj[i] = (c == 'H' ? 0 : c == 'P' ? 1 : 2);
    }
    // Winning gesture vs fj: H(0)<-S(2), P(1)<-H(0), S(2)<-P(1).
    auto wins = [](int bessie, int john) {
        return (bessie == 0 && john == 2) ||
               (bessie == 1 && john == 0) ||
               (bessie == 2 && john == 1);
    };

    // Rolling DP on rounds. cur[k][g], nxt[k][g].
    const int NEG = INT_MIN / 2;
    vector<vector<int>> cur(K + 1, vector<int>(3, NEG));
    for (int g = 0; g < 3; ++g) cur[0][g] = 0;

    for (int i = 0; i < N; ++i) {
        vector<vector<int>> nxt(K + 1, vector<int>(3, NEG));
        for (int k = 0; k <= K; ++k)
          for (int g = 0; g < 3; ++g) if (cur[k][g] > NEG / 2) {
            int v = cur[k][g] + (wins(g, fj[i]) ? 1 : 0);
            nxt[k][g] = max(nxt[k][g], v);             // keep gesture
            if (k < K)
              for (int g2 = 0; g2 < 3; ++g2) if (g2 != g) {
                int v2 = cur[k][g] + (wins(g2, fj[i]) ? 1 : 0);
                nxt[k + 1][g2] = max(nxt[k + 1][g2], v2);
              }
          }
        cur = move(nxt);
    }
    int best = 0;
    for (int k = 0; k <= K; ++k) for (int g = 0; g < 3; ++g) best = max(best, cur[k][g]);
    cout << best << "\n";
}

Pitfalls

Problem 3 — Cow Navigation

Statement

An N×N grid (N ≤ 20) has empty cells and haybales. Bessie starts at the lower-left cell facing either up or right (unknown to you) and must reach the upper-right cell. You give a fixed command sequence from {F, L, R}: F moves forward (no-op into a wall/haybale), L/R rotate. Once a copy of Bessie reaches the goal, she ignores future commands. Find the shortest sequence that succeeds for both starting orientations.

Constraints

Key idea

BFS on the joint state (posup, dirup, posright, dirright): one virtual Bessie for each starting orientation, advanced simultaneously by every command. State space ≤ N² · 4 · N² · 4 ≈ 2.5 · 10⁶ for N = 20, edges × 3 commands. Once one copy reaches (N,N) it "freezes" (use a goal sentinel for that copy so further commands don't change it). The answer is the shortest path to a state where both copies are at the goal.

Complexity target

O(N⁴ · 16 · 3) BFS edges ≈ 7.7 · 10⁶. Fits easily.

Reference solution (C++)

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

int N;
vector<string> g;
// Directions: 0=up, 1=right, 2=down, 3=left. dr, dc match "row 0 at top".
// We treat (1,1) at lower-left = grid row N-1, col 0; (N,N) = row 0, col N-1.
int dr[4] = {-1, 0, 1, 0};
int dc[4] = { 0, 1, 0,-1};

struct S { int r1,c1,d1, r2,c2,d2; };
bool atGoal(int r, int c) { return r == 0 && c == N - 1; }

int encode(const S& s) {
    return (((s.r1 * N + s.c1) * 4 + s.d1) * (N * N * 4))
         + ((s.r2 * N + s.c2) * 4 + s.d2);
}

S step(S s, int cmd) {
    auto move1 = [&](int& r, int& c, int& d) {
        if (atGoal(r, c)) return;          // frozen at goal
        if (cmd == 1) { d = (d + 3) & 3; return; }  // L
        if (cmd == 2) { d = (d + 1) & 3; return; }  // R
        int nr = r + dr[d], nc = c + dc[d];
        if (nr >= 0 && nr < N && nc >= 0 && nc < N && g[nr][nc] == 'E') { r = nr; c = nc; }
    };
    move1(s.r1, s.c1, s.d1);
    move1(s.r2, s.c2, s.d2);
    return s;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    g.assign(N, "");
    for (auto& r : g) cin >> r;
    // Copy 1 starts facing up (dir 0), copy 2 facing right (dir 1), both at (N-1, 0).
    S start{N - 1, 0, 0, N - 1, 0, 1};

    unordered_map<long long, int> dist;
    auto key = [&](const S& s) {
        return ((long long)encode(s));
    };
    queue<S> q; q.push(start); dist[key(start)] = 0;
    while (!q.empty()) {
        S s = q.front(); q.pop();
        if (atGoal(s.r1, s.c1) && atGoal(s.r2, s.c2)) {
            cout << dist[key(s)] << "\n"; return 0;
        }
        int d0 = dist[key(s)];
        for (int cmd = 0; cmd < 3; ++cmd) {
            S t = step(s, cmd);
            long long k = key(t);
            if (!dist.count(k)) { dist[k] = d0 + 1; q.push(t); }
        }
    }
    return 0;
}

Pitfalls

What Gold January 2017 was actually testing