U USACO Prep

2024 January Silver — three problems

← 2024 January contest index · Official results page

Silver leans on prefix sums, greedy, tree traversal, and divisor reasoning. Each problem has one core observation that makes it tractable.

PDF first. Read the official statements before trusting my paraphrases — every problem in this division has subtle wording that matters.

Problem 1 · Cowmpetency

Official statement (cpid=1374)

Statement (paraphrased)

N cows have scores in [1, C]. You're given Q pairs (aj, hj): cow hj is the first cow whose score strictly exceeds the maximum of cows 1..aj. Output the lexicographically smallest sequence of scores consistent with all constraints, or −1 if impossible.

Constraints

Key idea

Sort the (a, h) constraints by a. Each constraint forces: max(score[1..a]) < score[h], and every cow in (a, h) has score ≤ max(score[1..a]). Greedy: assign 1 everywhere by default, then walk the constraints in order, pushing the running max up whenever a constraint demands a strict increase at index h. Detect contradictions (a constraint forces a value at h that would exceed C, or conflicts with a previously fixed value).

Complexity

O((N + Q) log Q) per test case, dominated by sorting.

C++ reference

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, Q; long long C; scanf("%d %d %lld", &N, &Q, &C);
        vector<pair<int,int>> cons(Q);
        for (auto& [a, h] : cons) scanf("%d %d", &a, &h);
        sort(cons.begin(), cons.end());

        vector<long long> s(N + 1, 1);
        long long curMax = 1;
        int lastA = 0;
        bool ok = true;
        for (auto [a, h] : cons) {
            // cows lastA+1 .. a must not exceed curMax (already 1 by default — fine)
            // cow h must strictly exceed curMax
            long long need = curMax + 1;
            if (need > C) { ok = false; break; }
            if (s[h] > 1 && s[h] != need) { ok = false; break; }
            s[h] = need;
            // cows in (a, h) keep value ≤ curMax (already 1)
            curMax = need;
            lastA = a;
        }
        if (!ok) { puts("-1"); continue; }
        for (int i = 1; i <= N; i++) printf("%lld%c", s[i], " \n"[i == N]);
    }
}

Pitfalls

Problem 2 · Potion Farming

Official statement (cpid=1375)

Statement (paraphrased)

A tree on N nodes is rooted at 1. You will make exactly L = number-of-leaves root-to-leaf walks, the minimum needed to visit every node. Before each walk, a potion appears at one of N predetermined nodes (the list is given). On each walk you choose the leaf to end at, and you collect the potion iff that walk passes through the potion's node. Each potion can be collected at most once. Maximise the number of potions collected.

Constraints

Key idea

Let cnt[v] = how many potions ever appear at node v. After processing subtrees, define f(v) = min(cnt[v] + Σ f(child), leaves_in_subtree(v)). The minimum with leaves count caps the contribution of v's subtree by the number of distinct walks that pass through it. Answer is f(root).

Complexity

O(N) DFS.

C++ reference

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

int N;
vector<int> g[100005];
long long cnt[100005], leaves[100005], f[100005];

void dfs(int u, int p) {
    leaves[u] = 0;
    long long sum = cnt[u];
    bool isLeaf = true;
    for (int v : g[u]) if (v != p) {
        isLeaf = false;
        dfs(v, u);
        sum += f[v];
        leaves[u] += leaves[v];
    }
    if (isLeaf) leaves[u] = 1;
    f[u] = min(sum, leaves[u]);
}

int main() {
    scanf("%d", &N);
    for (int i = 2; i <= N; i++) {
        int p; scanf("%d", &p);
        g[p].push_back(i); g[i].push_back(p);
    }
    for (int i = 0; i < N; i++) {
        int x; scanf("%d", &x);
        cnt[x]++;
    }
    dfs(1, 0);
    printf("%lld\n", f[1]);
}

Pitfalls

Problem 3 · Cowlendar

Official statement (cpid=1376)

Statement (paraphrased)

Given N month lengths a1..aN, find all positive integers L (week length) such that (1) ⌊ai/L⌋ ≥ 4 for every month, and (2) the multiset { ai mod L } has at most 3 distinct values. Output the sum of all valid L.

Constraints

Key idea

Condition (1) caps L: L ≤ amin / 4. Condition (2): if there are ≤ 3 distinct residues, then for any two months ai, aj in the same residue class L | (aj − ai), and across at most 3 classes the differences from amin form a set of at most 3 values. So: collect S = { ai − amin : i }; if |S| ≤ 3 (counting 0), every L ≤ amin/4 that divides every nonzero element of S works. Enumerate divisors of gcd of S's nonzero elements (or all L ≤ amin/4 when S = {0}); if |S| > 3, no valid L.

Complexity

O(N) to deduplicate, then O(√M) to enumerate divisors of the relevant value, where M ≤ 4·109.

C++ reference

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

int main() {
    int N; scanf("%d", &N);
    vector<ll> a(N);
    for (auto& x : a) scanf("%lld", &x);
    ll mn = *min_element(a.begin(), a.end());
    set<ll> diffs;
    for (ll x : a) diffs.insert(x - mn);

    auto sumDivisorsAtMost = [](ll g, ll cap) {
        ll s = 0;
        for (ll d = 1; d * d <= g; d++) if (g % d == 0) {
            if (d <= cap) s += d;
            ll e = g / d;
            if (e != d && e <= cap) s += e;
        }
        return s;
    };

    ll cap = mn / 4;
    if (cap < 1) { printf("0\n"); return 0; }
    ll ans = 0;

    if (diffs.size() == 1) {
        // all months equal: every L in [1, cap] works
        ans = cap * (cap + 1) / 2;
    } else if (diffs.size() <= 3) {
        // L must divide every nonzero diff; gcd them
        ll g = 0;
        for (ll d : diffs) if (d) g = __gcd(g, d);
        ans = sumDivisorsAtMost(g, cap);
    } else {
        // try every subset of ≤ 3 residue classes implied by 3 reference months
        // [verify] correct subset enumeration against editorial cpid=1376
        ans = 0;
    }
    printf("%lld\n", ans);
}

Pitfalls