U USACO Prep

2022 January Bronze — three problems

← 2022 January contest index · Official results page

Bronze 2022-Jan is a Wordle-style simulation, a tiny game-theory search, and a feasibility/greedy on adjacent operations. The dominant skill is reading the spec carefully — Herdle in particular has a subtle yellow-count rule.

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 · Herdle

Official statement (cpid=1179)

Statement (paraphrased)

Two 3×3 grids of letters A–Z (cow breeds): a guess grid and the true grid. A square is green if guess[r][c] equals true[r][c]. A square is yellow if it is not green but its breed appears somewhere else in the true grid — with a multiplicity cap: if the guess has x copies of a breed and the true grid has y < x copies (after subtracting greens), only y of the remaining x guess squares are yellow. Output (greens, yellows) on two lines.

Constraints

Key idea

Two passes. Pass 1: mark greens, decrement both guess and true frequency tables for each green square so greens don't double-count. Pass 2: walk the remaining guess squares; for each, if the true frequency for that letter is still positive, mark yellow and decrement.

Complexity

O(9) per test.

C++ reference

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

int main() {
    char g[3][4], t[3][4];
    for (int i = 0; i < 3; i++) scanf("%s", g[i]);
    for (int i = 0; i < 3; i++) scanf("%s", t[i]);

    int green = 0, yellow = 0;
    int freqT[26] = {0}, freqG[26] = {0};
    bool isGreen[3][3] = {{false}};

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (g[i][j] == t[i][j]) { isGreen[i][j] = true; green++; }
            else { freqT[t[i][j] - 'A']++; freqG[g[i][j] - 'A']++; }

    // yellow count = sum over letters of min(freqG[c], freqT[c])
    for (int c = 0; c < 26; c++) yellow += min(freqG[c], freqT[c]);

    printf("%d\n%d\n", green, yellow);
    return 0;
}

Pitfalls

Problem 2 · Non-Transitive Dice

Official statement (cpid=1180)

Statement (paraphrased)

T test cases. Each test case gives two 4-sided dice A and B with face values in 1..10. Decide whether there exists a 4-sided die C (faces in 1..10, repeats allowed) such that A beats B, B beats C, and C beats A in the "more wins than losses across all 16 face-pairs, ties are re-rolled" sense. Print "yes" or "no".

Constraints

Key idea

Brute force C. There are at most 104 = 10 000 candidate C dice (4 faces each in 1..10). For each candidate, count A-vs-C wins (out of 16 pairs) and B-vs-C wins, plus a one-time A-vs-B count. If A beats B AND B beats C AND C beats A simultaneously, output yes. The "beats" relation here is "more wins than losses", since ties are re-rolled.

Complexity

O(104 · 16) per test = ~1.6·105.

C++ reference

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

int wins(const int *X, const int *Y) {  // does X beat Y?
    int w = 0, l = 0;
    for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) {
        if (X[i] > Y[j]) w++;
        else if (X[i] < Y[j]) l++;
    }
    return w > l;  // ties re-rolled, so just compare strict wins vs losses
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int A[4], B[4];
        for (int i = 0; i < 4; i++) scanf("%d", &A[i]);
        for (int i = 0; i < 4; i++) scanf("%d", &B[i]);
        if (!wins(A, B)) { printf("no\n"); continue; }  // need A>B as a premise
        bool ok = false;
        int C[4];
        for (C[0] = 1; C[0] <= 10 && !ok; C[0]++)
        for (C[1] = 1; C[1] <= 10 && !ok; C[1]++)
        for (C[2] = 1; C[2] <= 10 && !ok; C[2]++)
        for (C[3] = 1; C[3] <= 10 && !ok; C[3]++)
            if (wins(B, C) && wins(C, A)) ok = true;
        printf(ok ? "yes\n" : "no\n");
    }
}

Pitfalls

Problem 3 · Drought

Official statement (cpid=1181)

Statement (paraphrased)

N cows in a row with hunger levels h1,…,hN. One bag of corn lets you decrease the hunger of two adjacent cows by 1 each (hunger cannot go negative). Minimum bags so all cows have the same hunger level, or −1 if impossible. T test cases.

Constraints

Key idea

The target value must equal min(h). One operation decreases two adjacent values by 1, so it preserves parity of every "alternating" sum. For N=1: 0 bags. For N=2: only possible if h1=h2. For N≥3: the target is min(h) and we can simulate greedily left-to-right: at position i, the excess e = hi − target must be pushed to position i+1 (cost e bags). If after the sweep hN ≠ target, output −1. Total bags = Σ excess processed.

For N even and N=2, parity check is the entire feasibility test; for N≥3 greedy handles it cleanly because any leftover at the right end is genuinely impossible to clear.

Complexity

O(N) per test case.

C++ reference

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        vector<long long> h(N);
        long long mn = LLONG_MAX;
        for (int i = 0; i < N; i++) { scanf("%lld", &h[i]); mn = min(mn, h[i]); }

        if (N == 1) { printf("0\n"); continue; }
        if (N == 2) { printf("%s\n", h[0] == h[1] ? "0" : "-1"); continue; }

        long long bags = 0;
        bool ok = true;
        for (int i = 0; i < N - 1 && ok; i++) {
            long long ex = h[i] - mn;
            if (ex < 0) { ok = false; break; }   // can't happen since mn = min
            bags += ex;
            h[i + 1] -= ex;
            if (h[i + 1] < mn) { ok = false; break; }
        }
        if (ok && h[N - 1] != mn) ok = false;
        printf("%lld\n", ok ? bags : -1LL);
    }
}

Pitfalls