USACO 2017 February · Bronze · all three problems

← Full February 2017 set · Official results

Problem 1 — Why Did the Cow Cross the Road

Statement

Farmer John logs N sightings of his cows. Each sighting is a pair (id, side) where side is 0 or 1 (which side of the road). A "confirmed crossing" occurs when two consecutive sightings of the same cow are on different sides. Output the total number of confirmed crossings.

Constraints

• 1 ≤ N ≤ 100.
• Cow IDs are integers in [1, 10].
• Side is 0 or 1.
• Time limit: 2s.

Key idea

Track the last known side for each of the (≤10) cows. For every new sighting, if the cow has a previously recorded side and it differs, increment the answer. Then update its last side.

Complexity target

O(N) time, O(maxId) memory. Trivially in limits.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // last[id] = -1 means "no prior sighting"; otherwise 0 or 1.
    int N; cin >> N;
    vector<int> last(11, -1);
    int crossings = 0;
    for (int i = 0; i < N; ++i) {
        int id, side; cin >> id >> side;
        if (last[id] != -1 && last[id] != side) ++crossings;
        last[id] = side;
    }
    cout << crossings << "\n";
}

Pitfalls

• Only consecutive sightings count. Don't compare the first and last sighting of a cow directly — count crossings step by step.
• The very first sighting of any cow is not a crossing. Initialize "last side" to a sentinel.
• IDs go up to 10. Don't assume 1-indexed contiguous IDs in a tight array without sizing for 11 slots.

Problem 2 — Why Did the Cow Cross the Road II

Statement

26 cows (named A–Z) cross a circular road at 52 distinct points. The input is a single 52-character string giving the points in clockwise order; each uppercase letter appears exactly twice (the cow's entry and exit). Two cows' chords must cross iff exactly one endpoint of one chord lies strictly between the two endpoints of the other. Count such crossing pairs.

Constraints

• String length is exactly 52, each of A–Z appears exactly twice.
• Time limit: 2s.

Key idea

For each pair of letters (a, b), find the two positions of a and the two positions of b. They form a crossing pair iff exactly one of b's positions lies strictly between a's two positions in the 52-char string (treating it linearly is fine — the chord-cross condition is the same as the classic "open parenthesis interleaving" test). There are only C(26,2) = 325 pairs, brute force.

Complexity target

O(26²) = O(1). Effectively instant.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    // pos[c] = (first index, second index) of letter c.
    array<pair<int,int>, 26> pos;
    for (auto& p : pos) p = {-1, -1};
    for (int i = 0; i < (int)s.size(); ++i) {
        int c = s[i] - 'A';
        if (pos[c].first == -1) pos[c].first = i;
        else                    pos[c].second = i;
    }
    int ans = 0;
    for (int a = 0; a < 26; ++a)
      for (int b = a + 1; b < 26; ++b) {
        auto [a1, a2] = pos[a];
        auto [b1, b2] = pos[b];
        int inside = 0;
        if (a1 < b1 && b1 < a2) ++inside;
        if (a1 < b2 && b2 < a2) ++inside;
        if (inside == 1) ++ans;
      }
    cout << ans << "\n";
}

Pitfalls

• Linearizing the circle is fine here. Cutting the circle at the start of the string preserves the "exactly one endpoint inside the other interval" predicate.
• "Inside" means strictly inside. Endpoints are distinct so strict inequality is fine — but be careful when adapting to general inputs.
• Don't overcount. Iterate ordered pairs (a<b) once.

Problem 3 — Why Did the Cow Cross the Road III

Statement

N cows arrive at a single-server gate. Cow i arrives at time a_i and needs d_i seconds of questioning. Cows are served first-come-first-served (sorted by arrival; arrivals are distinct). The server is idle between cows. Output the time at which the last cow finishes.

Constraints

• 1 ≤ N ≤ 100.
• 1 ≤ a_i, d_i ≤ 10⁶.
• Time limit: 2s.

Key idea

Sort cows by arrival time. Maintain t = current server time, initialized to 0. For each cow: t = max(t, ai) + di. After the loop, t is the answer.

Complexity target

O(N log N) for the sort. Trivial under N ≤ 100.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<pair<ll,ll>> cows(N);   // (arrival, duration)
    for (auto& [a, d] : cows) cin >> a >> d;
    sort(cows.begin(), cows.end());

    ll t = 0;
    for (auto [a, d] : cows) {
        t = max(t, a) + d;
    }
    cout << t << "\n";
}

Pitfalls

• Input is not pre-sorted. The statement gives cows in arbitrary order; sort by arrival before sweeping.
• The server may be idle. If a cow arrives after the previous finished, jump t forward to her arrival.
• Use long long for safety. N · max(d) ≤ 10⁸, which fits in int, but defensive 64-bit costs nothing.

What Bronze February 2017 was actually testing

• P1 — last-seen bookkeeping. Pure simulation; a single array of size 11 suffices.
• P2 — chord crossing on a circle. The "interval interleaving" predicate is the contest staple — recognize it and you have a 20-line solution.
• P3 — single-server FCFS queue. Classic running-max-then-add pattern, the simplest scheduling primitive.