U USACO Prep

USACO 2017 US Open · Bronze · all three problems

← Full 2017 US Open set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=open17results. 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 — The Lost Cow

Statement

Farmer John stands at integer position x on a number line. Bessie is hiding at integer position y. FJ searches with a fixed zigzag rule: step 1 to the right, step 2 to the left, step 4 to the right, step 8 to the left, … doubling and alternating direction. He stops the instant his current sweep covers y (i.e. y lies between his previous position and his new position, inclusive). Output the total distance he walks.

Constraints

Key idea

Just simulate. At step k (k = 0, 1, 2, …) FJ moves a signed distance of (k even ? +1 : −1) · 2k from his current position. After each step, check whether y lies on the closed segment between the old and new position. If yes, the total distance is (previous accumulated distance) + |y − old position|; otherwise add 2k and continue. Because the search is guaranteed to find y within roughly 9|x−y| distance, you never need k larger than ~12.

Complexity target

O(log |x − y|) steps; well under a microsecond.

Reference solution (C++)

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

int main() {
    int x, y; cin >> x >> y;
    long long pos = x, dist = 0, step = 1;
    int sign = +1; // first move is to the right
    while (true) {
        long long npos = pos + (long long)sign * step;
        long long lo = min(pos, npos), hi = max(pos, npos);
        if (lo <= y && y <= hi) {
            dist += abs(y - pos);
            break;
        }
        dist += step;
        pos = npos;
        step *= 2;
        sign = -sign;
    }
    cout << dist << "\n";
}

Pitfalls

Problem 2 — Bovine Genomics

Statement

There are N spotty cows and N plain cows. Each has a genome of length M over the alphabet {A, C, G, T}. Count the number of column indices j (0-indexed or 1-indexed, your choice) such that the multiset of characters at column j among the spotty cows is disjoint from the multiset of characters at column j among the plain cows. (Equivalently: no character appears at column j in both groups.) Such a column "explains" spottiness on its own.

Constraints

Key idea

For each column j, build two 4-bit masks — one of letters appearing in the spotty group at j, and one of letters appearing in the plain group. The column qualifies if the AND of the two masks is 0. O(N·M) over a tiny alphabet.

Complexity target

O(N · M) = 104. Trivial.

Reference solution (C++)

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

int idx(char c) {
    switch (c) { case 'A': return 0; case 'C': return 1;
                 case 'G': return 2; default: return 3; } // 'T'
}

int main() {
    int N, M; cin >> N >> M;
    vector<string> spot(N), plain(N);
    for (auto& s : spot)  cin >> s;
    for (auto& s : plain) cin >> s;

    int ans = 0;
    for (int j = 0; j < M; ++j) {
        int sm = 0, pm = 0;
        for (int i = 0; i < N; ++i) sm |= 1 << idx(spot[i][j]);
        for (int i = 0; i < N; ++i) pm |= 1 << idx(plain[i][j]);
        if ((sm & pm) == 0) ++ans;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Modern Art

Statement

Picowso paints 9 axis-aligned rectangles, in colors 1 through 9, on an N×N canvas. The canvas starts as zeros. Each color is used at most once, and later colors can overwrite earlier ones. Given the final canvas, count how many of the 9 colors could have been the very first color painted — i.e. colors that are not required to lie on top of any other visible color.

Constraints

Key idea

For each visible color c, compute the bounding box of its visible cells. If every cell inside that bounding box is either color c or 0, then color c could be the first painted (nothing sits beneath it). If any cell inside is a different non-zero color, then c had to be painted before that other color, so c was not first. Count colors whose bounding box has no foreign non-zero cells. (Colors that don't appear at all in the grid are buried under others and cannot be "first painted" in the visible sense — check the official sample to confirm.)

Complexity target

O(N2 · 9) = 900. Trivial.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<vector<int>> g(N, vector<int>(N));
    for (auto& r : g) for (auto& x : r) cin >> x;

    // Per color c=1..9: bounding box of cells where g==c.
    int lo_r[10], hi_r[10], lo_c[10], hi_c[10];
    bool present[10] = {};
    for (int c = 1; c <= 9; ++c) {
        lo_r[c] = lo_c[c] = INT_MAX;
        hi_r[c] = hi_c[c] = INT_MIN;
    }
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        int c = g[i][j];
        if (c == 0) continue;
        present[c] = true;
        lo_r[c] = min(lo_r[c], i); hi_r[c] = max(hi_r[c], i);
        lo_c[c] = min(lo_c[c], j); hi_c[c] = max(hi_c[c], j);
    }

    int ans = 0;
    for (int c = 1; c <= 9; ++c) {
        if (!present[c]) continue;
        bool first_ok = true;
        for (int i = lo_r[c]; i <= hi_r[c] && first_ok; ++i)
            for (int j = lo_c[c]; j <= hi_c[c] && first_ok; ++j)
                if (g[i][j] != 0 && g[i][j] != c) first_ok = false;
        if (first_ok) ++ans;
    }
    cout << ans << "\n";
}

Pitfalls

What Bronze 2017 US Open was actually testing