U USACO Prep

USACO 2015 January · Bronze · all four problems

← Full January 2015 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=jan15results. 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. Bronze in Jan 2015 was a 4-problem set, unlike the now-standard 3.

Problem 1 — Cow Routing

Statement

Air Bovinia owns N airline routes. Each route is an ordered list of cities with a fixed cost; if Bessie uses any portion of a route she pays the full cost. She may board at any city along the route and disembark at any later city along the same route. She wants to travel from city A to city B using exactly one route. Output the minimum cost, or -1 if no single route covers her trip.

Constraints

Key idea

For each route, find the position of A and the position of B (if both exist) and check that A appears before B. If so, that route is usable for cost = route.cost. Take the minimum across all routes.

Complexity target

O(N · L) where L is max route length — at most 250,000 ops.

Reference solution (C++)

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

int main() {
    freopen("cowroute.in", "r", stdin);
    freopen("cowroute.out", "w", stdout);
    int A, B, N; cin >> A >> B >> N;

    int best = INT_MAX;
    for (int i = 0; i < N; ++i) {
        int cost, k; cin >> cost >> k;
        vector<int> route(k);
        for (int j = 0; j < k; ++j) cin >> route[j];
        int posA = -1, posB = -1;
        for (int j = 0; j < k; ++j) {
            if (route[j] == A) posA = j;
            if (route[j] == B && posA != -1 && posB == -1) posB = j;
        }
        if (posA != -1 && posB != -1 && posA < posB)
            best = min(best, cost);
    }
    cout << (best == INT_MAX ? -1 : best) << "\n";
}

Pitfalls

Problem 2 — Cow Routing II

Statement

Same setup as Problem 1, but Bessie may use up to two routes (each at most once). Output the minimum total cost from A to B, or -1 if even two routes cannot get her there.

Constraints

Key idea

Enumerate pairs (i, j) of routes and an intermediate city C that lies on both: route i must contain A then C in order, route j must contain C then B in order. With N ≤ 500 and L ≤ 500, the worst case is N² · L ≈ 1.25 × 10⁸ which barely fits; use sets to find common cities efficiently, or just iterate. Also handle the single-route case (reuse Problem 1's check) and take the minimum.

Complexity target

O(N² · L) in the worst case; cleaner: O(N · L · log L) using sets keyed by city.

Reference solution (C++)

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

int N, A, B;
vector<int> cost;
vector<vector<int>> rt;
vector<unordered_map<int,int>> pos; // city -> index in route

int main() {
    freopen("cowroute.in","r",stdin); freopen("cowroute.out","w",stdout);
    cin >> A >> B >> N;
    cost.resize(N); rt.resize(N); pos.resize(N);
    for (int i = 0; i < N; ++i) {
        int k; cin >> cost[i] >> k;
        rt[i].resize(k);
        for (int j = 0; j < k; ++j) { cin >> rt[i][j]; pos[i][rt[i][j]] = j; }
    }
    int best = INT_MAX;
    // single route
    for (int i = 0; i < N; ++i)
        if (pos[i].count(A) && pos[i].count(B) && pos[i][A] < pos[i][B])
            best = min(best, cost[i]);
    // two routes connected via some intermediate C
    for (int i = 0; i < N; ++i) if (pos[i].count(A))
        for (int j = 0; j < N; ++j) if (i != j && pos[j].count(B))
            for (auto &kv : pos[i])
                if (kv.second > pos[i][A] && pos[j].count(kv.first) && pos[j][kv.first] < pos[j][B]) {
                    best = min(best, cost[i] + cost[j]); break;
                }
    cout << (best == INT_MAX ? -1 : best) << "\n";
}

Pitfalls

Problem 3 — It's All About the Base

Statement

Bessie wrote the same integer N in two different bases X and Y (both in [10, 15000]); in each base the result was a 3-digit number with each digit in [1, 9]. Given the two 3-digit sequences (as base-10 decimal numbers from the input — e.g. "419" meaning digits 4, 1, 9), recover X and Y. A unique solution is guaranteed. K test cases.

Constraints

Key idea

A 3-digit number with digits (a, b, c) in base X equals a·X² + b·X + c, a quadratic in X. For each candidate X in [10, 15000] compute N = a·X² + b·X + c and store in a hash map N → X. Then iterate candidate Y in [10, 15000], compute M = a'·Y² + b'·Y + c', and look it up in the map. The unique pair (X, Y) with the same N is the answer. O(R) per test (R = 15000).

Complexity target

O(K · R) with hash map; R ≤ 15000.

Reference solution (C++)

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

int main() {
    freopen("whatbase.in","r",stdin); freopen("whatbase.out","w",stdout);
    int K; cin >> K;
    while (K--) {
        string sa, sb; cin >> sa >> sb;
        int a1 = sa[0]-'0', a2 = sa[1]-'0', a3 = sa[2]-'0';
        int b1 = sb[0]-'0', b2 = sb[1]-'0', b3 = sb[2]-'0';
        unordered_map<long long,int> seen;
        for (int X = 10; X <= 15000; ++X) {
            long long N = 1LL*a1*X*X + 1LL*a2*X + a3;
            seen[N] = X;
        }
        int ansX = -1, ansY = -1;
        for (int Y = 10; Y <= 15000 && ansY == -1; ++Y) {
            long long M = 1LL*b1*Y*Y + 1LL*b2*Y + b3;
            auto it = seen.find(M);
            if (it != seen.end() && it->second != Y) { ansX = it->second; ansY = Y; }
        }
        cout << ansX << " " << ansY << "\n";
    }
}

Pitfalls

Problem 4 — Meeting Time

Statement

A DAG of N fields (numbered 1..N with edges only from low index to high). M directed downhill paths, each carrying two weights: Bessie's traversal time C and Elsie's traversal time D. Bessie and Elsie leave field 1 at the same moment and want to both arrive at field N at the same moment. Output the smallest such common arrival time, or IMPOSSIBLE if no pair of (possibly different) paths of equal total length exists.

Constraints

Key idea

For each vertex v keep two bit-sets: reachB[v] = set of total Bessie-times for any path from 1 to v, reachE[v] = similar for Elsie. Both sets grow by topological-order DP. Path totals are at most 15 · 1000 = 15000, so a bitset of length 15001 suffices. Answer = smallest t in reachB[N] ∩ reachE[N].

Complexity target

O(M · T / 64) with T = 15001 — instant.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
const int T = 16005;

int main() {
    freopen("meeting.in","r",stdin); freopen("meeting.out","w",stdout);
    int N, M; cin >> N >> M;
    vector<tuple<int,int,int>> outB[17], outE[17]; // (to, weight) per source
    vector<bitset<T>> B(N+1), E(N+1);
    B[1].set(0); E[1].set(0);
    vector<vector<tuple<int,int,int>>> adj(N+1); // to, c, d
    for (int i = 0; i < M; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d; // a < b
        adj[a].push_back({b, c, d});
    }
    for (int u = 1; u <= N; ++u)
        for (auto [v, c, d] : adj[u]) {
            B[v] |= (B[u] << c);
            E[v] |= (E[u] << d);
        }
    bitset<T> both = B[N] & E[N];
    int ans = -1;
    for (int t = 1; t < T; ++t) if (both[t]) { ans = t; break; }
    if (ans == -1) cout << "IMPOSSIBLE\n"; else cout << ans << "\n";
}

Pitfalls

What Bronze January 2015 was actually testing