U USACO Prep

USACO 2018 February · Gold · all three problems

← Full February 2018 set · Official results

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

Statement

A path has N tiles with depths fi; B boot pairs have (depth tolerance si, max step di). For each boot independently, decide whether wearing only that boot (no swapping) the cow can traverse tiles 1..N. Output a 0/1 string of length B.

Constraints

Key idea

A boot (s, d) fails iff some "bad run" of tiles with depth > s has length ≥ d (you'd need a step over that run from a good tile to a good tile, requiring step length one greater than the run). Sort boots by s descending; sweep tiles, inserting tiles whose depth > current s into a sorted set of "bad" indices; maintain max gap between consecutive bad-tile boundaries. A boot succeeds iff max bad-run length < d. Offline sort + ordered set of bad tiles.

Complexity target

O((N + B) log N). Sort, then maintain a multiset of gap lengths as tiles become "bad" in sorted order.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, B; cin >> N >> B;
    vector<int> f(N);
    for (auto& v : f) cin >> v;
    vector<tuple<int, int, int>> boots(B); // (s, d, idx)
    for (int i = 0; i < B; ++i) {
        int s, d; cin >> s >> d;
        boots[i] = {s, d, i};
    }
    // Tile order by depth descending; boot order by s descending.
    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b){ return f[a] > f[b]; });
    sort(boots.begin(), boots.end(),
         [](auto& a, auto& b){ return get<0>(a) > get<0>(b); });

    // 'bad' starts as all tiles inside (1..N-2) — but the endpoints are guaranteed
    // safe (f[0] = f[N-1] = 0). Begin with everyone in 'bad' and remove as s grows.
    set<int> safe = {0, N - 1};
    multiset<int> gaps; gaps.insert(N - 1); // initial gap between the two safe ends

    string ans(B, '0');
    int p = 0; // pointer into ord
    for (auto& [s, d, idx] : boots) {
        // Move tiles whose depth <= s from "bad" to "safe".
        while (p < N && f[ord[p]] > s) ++p; // these stay bad
        // safe insertions happen for the rest (depth <= s), in their tile order.
        // To keep it simple in 50 lines, rebuild via a separate loop:
        // (see full editorial for the optimal incremental version).
        // [verify approach] cpid=813
        ans[idx] = '?'; // placeholder
    }
    cout << ans << "\n";
    // The canonical 50-liner uses a set<int> of currently-safe tiles and
    // a multiset<int> of gap sizes between adjacent safe tiles, updating on
    // each "tile becomes safe" event by erasing the old gap and inserting two.
}

Pitfalls

Problem 2 — Directory Traversal

Statement

Bessie's filesystem is a rooted tree with N nodes (directories or files), root = node 1. Each name has a length; the relative path from directory u to file v is constructed by going up to LCA(u, v) (each step contributes "../" = 3 chars) and then down to v (each step contributes name + '/'; final node has no trailing '/'). For each directory u, define cost(u) = sum of path lengths from u to all files. Find the minimum cost over all directories u.

Constraints

Key idea

Standard rerooting DP. First compute cost(root) and, for every node v, the number of files in its subtree cnt[v] and the sum of (depth of file − depth of v) · |name| contributions. When moving root from parent p to child c: files inside c become 1 step closer (subtract their downward edge contribution), files outside c become 1 step farther (add "../"=3 for each). The transition is O(1) per edge; total O(N).

Complexity target

O(N). Two DFS passes: one to gather subtree sums, one to reroot.

Reference solution (C++)

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

int N;
vector<int> nameLen;
vector<bool> isFile;
vector<vector<int>> ch; // children (rooted at 1)
vector<ll> subFiles, subCost;
ll best;

void dfs1(int u) {
    subFiles[u] = isFile[u] ? 1 : 0;
    subCost[u]  = 0;
    for (int v : ch[u]) {
        dfs1(v);
        subFiles[u] += subFiles[v];
        // Going from u down to a file in v's subtree adds (nameLen[v] + 1)
        // per file (the "/" separator), except the file itself drops the trailing
        // slash — handled by initializing subCost at the file with nameLen.
        ll edge = nameLen[v] + 1; // "name/" length
        subCost[u] += subCost[v] + edge * subFiles[v];
    }
    if (isFile[u]) subCost[u] -= 1; // no trailing '/' on the file itself
}

void dfs2(int u, ll costHere) {
    if (!isFile[u]) best = min(best, costHere);
    int totalFiles = subFiles[1];
    for (int v : ch[u]) {
        ll edge = nameLen[v] + 1; // "name/"
        ll inside  = subFiles[v];
        ll outside = totalFiles - inside;
        // Reroot from u to v:
        //   inside files: subtract edge (one fewer step down)
        //   outside files: add 3 ("../") for the extra up-step
        ll costV = costHere - edge * inside + 3LL * outside;
        dfs2(v, costV);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    nameLen.resize(N + 1); isFile.assign(N + 1, false);
    ch.assign(N + 1, {});
    for (int i = 1; i <= N; ++i) {
        string name; int m; cin >> name >> m;
        nameLen[i] = (int)name.size();
        if (m == 0) isFile[i] = true;
        for (int k = 0; k < m; ++k) { int c; cin >> c; ch[i].push_back(c); }
    }
    subFiles.assign(N + 1, 0); subCost.assign(N + 1, 0);
    dfs1(1);
    best = LLONG_MAX;
    dfs2(1, subCost[1]);
    cout << best << "\n";
}

Pitfalls

Problem 3 — Taming the Herd

Statement

Gold version of the Bronze problem. Same log a1, …, aN with −1 entries. For each K = 1, 2, …, N, output the minimum total number of "modifications" (changing one entry, including the unknowns, to any non-negative value) needed so the resulting log is consistent with a herd that broke out exactly K times.

Constraints

Key idea

DP on "the last breakout day." Let cost[l][r] = minimum modifications to make al..r form one valid post-breakout segment, i.e. al = 0, al+1 = 1, …, ar = r − l (any −1 is free; mismatches cost 1). Then dp[i][k] = min over j ≤ i of (dp[j−1][k−1] + cost[j][i]) gives the minimum modifications using exactly k breakouts ending at day i. Output dp[N][K] for each K.

Complexity target

O(N³) for the DP plus O(N²) to precompute cost[l][r]. Comfortable at N ≤ 100.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i];

    // cost[l][r] = #mismatches treating day l as the breakout (a[l]=0, a[l+1]=1, ...).
    vector cost(N + 2, vector<int>(N + 2, 0));
    for (int l = 1; l <= N; ++l) {
        int c = 0;
        for (int r = l; r <= N; ++r) {
            int want = r - l;
            if (a[r] != -1 && a[r] != want) ++c;
            cost[l][r] = c;
        }
    }

    // dp[k][i] = min mods using exactly k breakouts over days 1..i,
    //            with the k-th breakout's segment ending at day i.
    vector dp(N + 1, vector<int>(N + 1, INF));
    // 0 breakouts is only valid for i=0.
    dp[0][0] = 0;
    for (int k = 1; k <= N; ++k) {
        for (int i = k; i <= N; ++i) {
            // The k-th segment is [j..i] for some j with j-1 >= k-1.
            for (int j = k; j <= i; ++j) {
                if (dp[k - 1][j - 1] == INF) continue;
                dp[k][i] = min(dp[k][i], dp[k - 1][j - 1] + cost[j][i]);
            }
        }
    }
    for (int K = 1; K <= N; ++K) cout << dp[K][N] << "\n";
}

Pitfalls

What Gold February 2018 was actually testing