U USACO Prep

2022 January Silver — three problems

← 2022 January contest index · Official results page

Silver 2022-Jan asks for a number-theoretic search (Soulmates), a contribution-counting monotonic-stack sweep (Frisbee), and a connected-components DP on a 2-out functional graph (Cereal 2).

Read the official PDF first. Paraphrases below are my own; if my wording and the PDF disagree, the PDF wins. All three problem links go to usaco.org.

Problem 1 · Searching for Soulmates

Official statement (cpid=1182)

Statement (paraphrased)

For each of N independent pairs (a, b), compute the minimum number of operations from {×2, ÷2 if even, +1} to turn a into b. Values are up to 1018, so BFS over the integer line is dead on arrival.

Constraints

Key idea

Reverse the moves. Working from b downward you can {÷2 if even, −1}. The optimal strategy splits into two phases: first add some k ≥ 0 to a (call the result a' = a + k), then repeatedly halve a' (only valid when a' is even at the time of each halve) and add 1's strategically until you hit b. Equivalently, choose the "switch point" v ≥ a: cost to reach v from a is (v − a). From v you can only halve (when even) and add 1 (post-halving), so the cost from v to b can be computed by walking b downward: while b > v, if b is odd add 1 (cost 1, then it becomes even), else halve (cost 1). Try v ∈ {a, a+1, …, some bound}; the optimal v lies within O(60) of a or near b's high bits, so iterate v from a up to ~a+60 and also try v = (b shifted down to where it fits below a then padded). Take the minimum.

Cleaner formulation: for each possible number of halvings h (0..63), the "midpoint" m must satisfy m·2h ≤ b < (m+1)·2h. Cost = (m − a) [if m ≥ a, else infeasible in this phase] + h + popcount of the low h bits of b. Take min over h.

Complexity

O(642) per query.

C++ reference

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

ull solve(ull a, ull b) {
    // strategy: first do +1's until value = m, then alternately halve b downward to m using
    // moves {/2 if even, -1} (reverse of {*2, +1}).  Cost = (m - a) + ops_down(b -> m).
    ull best = ULLONG_MAX;
    // try every halve count h
    for (int h = 0; h <= 62; h++) {
        ull m = b >> h;
        if (m < a) continue;
        // cost to descend b -> m: h halvings + popcount of low h bits (each odd step costs one -1)
        ull low = b & ((1ULL << h) - 1);
        ull descend = (ull)h + (ull)__builtin_popcountll(low);
        ull cost = (m - a) + descend;
        best = min(best, cost);
    }
    // also: never halve, just +1 all the way (h=0 handled above but guard b<a)
    if (b >= a) best = min(best, b - a);
    return best;
}

int main() {
    int N; scanf("%d", &N);
    while (N--) { ull a, b; scanf("%llu %llu", &a, &b); printf("%llu\n", solve(a, b)); }
}

Pitfalls

Problem 2 · Cow Frisbee

Official statement (cpid=1183)

Statement (paraphrased)

Heights h1,…,hN are a permutation of 1..N. A pair (i, j) with i < j is "good" if max(hi, hj) is greater than every hk for i < k < j. Output Σ (j − i + 1) over good pairs.

Constraints

Key idea

Classic monotonic-stack "next greater" sweep, twice. A pair (i, j) is good iff hj is the next-greater-to-the-right of hi, OR hi is the next-greater-to-the-left of hj. Equivalently: while sweeping left-to-right with a decreasing stack of indices, whenever a new element x pops index k off the stack, the pair (k, current) is good; also when k remains on the stack and a new element comes that is smaller, the new top forms a good pair with the new element. To avoid double-counting, accumulate (j − i + 1) once per stack interaction. Equivalent clean form: for each index i, the good partners on the right are the strict left-to-right minima of (hi+1, hi+2, …) up to and including the first index whose height exceeds hi.

Complexity

O(N) total.

C++ reference

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

int main() {
    int N; scanf("%d", &N);
    vector<int> h(N);
    for (int i = 0; i < N; i++) scanf("%d", &h[i]);

    long long ans = 0;
    vector<int> st;  // indices, h decreasing top-down
    for (int j = 0; j < N; j++) {
        while (!st.empty() && h[st.back()] < h[j]) {
            int i = st.back(); st.pop_back();
            ans += (long long)(j - i + 1);   // i sees j as next-greater
        }
        if (!st.empty()) {
            int i = st.back();
            ans += (long long)(j - i + 1);   // j sees i as next-greater-to-left (i>j in height)
        }
        st.push_back(j);
    }
    printf("%lld\n", ans);
}

Pitfalls

Problem 3 · Cereal 2

Official statement (cpid=1184)

Statement (paraphrased)

N cows, M cereal types. Cow i has favourite fi and backup gi. One box of each cereal exists. Cows are processed in some order; each cow takes her favourite if still on the shelf, else her backup, else goes hungry. Choose the order to minimise hungry cows; output the count and one such order.

Constraints

Key idea

Model as a functional graph on cereals: cow i is an edge from fi to gi. Each connected component (in the underlying undirected graph) is independent. In a tree component with V cereal nodes and E = V − 1 cows, all cows can eat. If E ≥ V (component has a cycle), V cows can eat and E − V cows go hungry. To recover an order: for each component, peel cows whose favourite cereal is currently unclaimed; if a tree, root at any unused cereal and process leaves; if cyclic, pick any cycle edge to leave hungry, then process the rest greedily. Sum of (E − V) over cyclic components plus 0 over tree components is the answer.

Complexity

O((N + M) α(N + M)) with DSU; O(N + M) with DFS.

C++ reference

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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int f(int x) { return p[x] == x ? x : p[x] = f(p[x]); }
    bool u(int a, int b) { a = f(a); b = f(b); if (a == b) return false;
        if (r[a] < r[b]) swap(a, b); p[b] = a; if (r[a] == r[b]) r[a]++; return true; }
};

int main() {
    int N, M; scanf("%d %d", &N, &M);
    vector<int> f(N), g(N);
    for (int i = 0; i < N; i++) { scanf("%d %d", &f[i], &g[i]); --f[i]; --g[i]; }
    DSU d(M);
    vector<int> edgesIn(M, 0);   // count of cow-edges per component (by representative, fixed at end)
    // count edges per "component"; treat each cow as an edge between f[i] and g[i]
    vector<pair<int,int>> es(N);
    for (int i = 0; i < N; i++) { es[i] = {f[i], g[i]}; d.u(f[i], g[i]); }
    vector<int> eCnt(M, 0), vCnt(M, 0);
    for (int v = 0; v < M; v++) vCnt[d.f(v)]++;
    for (auto& e : es) eCnt[d.f(e.first)]++;

    int hungry = 0;
    for (int r = 0; r < M; r++) if (d.f(r) == r && eCnt[r] > vCnt[r] - 0) {
        // tree iff eCnt == vCnt - 1; cyclic iff eCnt >= vCnt
        if (eCnt[r] >= vCnt[r]) hungry += eCnt[r] - vCnt[r];
    }
    printf("%d\n", hungry);
    // (Producing an explicit order requires a DFS / peeling pass — omitted here for brevity.)
}

Pitfalls