USACO 2026 Second Contest Bronze Division - Moo Hunt#

Problem link: here

Problem Solution#

Each cell holds M or O, and a moove $(x,y,z)$ earns a point exactly when $s_x=M$ and $s_y=s_z=O$. Over all $2^N$ boards we must report the maximum score and the number of boards attaining it.

There are few boards. Since $N\le 20$, there are at most $2^{20}\approx 10^6$ boards, so we can afford to evaluate every one. The real danger is the mooves: replaying all $K\le 2\cdot 10^5$ mooves for every board would need $2^{20}\cdot 2\cdot 10^5$ operations --- hopeless.

Mooves can be deduplicated. A moove's contribution depends only on the characters at its three cells, and the condition $s_y=s_z=O$ is symmetric in $y$ and $z$: the triples $(x,y,z)$ and $(x,z,y)$ always score together. So we canonicalize each moove by swapping $y,z$ when $y>z$, and store multiplicities in a table $cnt[x][y][z]$ with $y \lt z$. There are at most $N\binom{N-1}{2}=3420$ distinct canonical triples, so the table fully replaces the move list.

Encode a board as a bitmask: bit $i-1$ is set iff $s_i=M$. For each mask, its score is $$ \sum_{\substack{x:\ s_x=M\ y \lt z:\ s_y=s_z=O}} cnt[x][y][z], $$ computed by looping over M-cells $x$ and pairs of O-cells $y \lt z$. Because $x$ is M while $y,z$ are O, the three indices are automatically distinct, which matches the guarantee that a moove taps pairwise different cells. While enumerating masks we keep the best score seen and count how many masks achieve it.

Complexity-wise, reading input costs $O(K)$. For the enumeration, fix a canonical triple $(x,y,z)$ with distinct cells: it is inspected exactly in the $2^{N-3}$ masks where $x$ is M and $y,z$ are O. Hence the total number of inner-loop steps is $N\binom{N-1}{2}\cdot 2^{N-3}\approx 4.5\cdot 10^8$ --- only cheap array reads, which runs comfortably in time in C++. Memory is $O(N^3)$. Both outputs fit in 32-bit integers (the score is at most $K\le 2\cdot 10^5$, the count at most $2^{20}$), though using 64-bit types is a safe habit.

The essence of the solution is combining a small search space ($2^N$ boards) with a compression of the input ($K$ mooves into at most 3420 weighted triples). Without the deduplication step, the same brute force would be orders of magnitude too slow --- a common trap whenever the input contains many equivalent items.

Source code#

The source code for the solution in C++ can be seen below.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 20;

int moove_count[MAX_N + 1][MAX_N + 1][MAX_N + 1];

int m_positions[MAX_N + 1];
int o_positions[MAX_N + 1];

void solve() {
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < k; i++) {
        int x, y, z;
        cin >> x >> y >> z;

        if (y > z) {
            swap(y, z);
        }

        moove_count[x][y][z]++;
    }

    int maximum_score = -1;
    int board_count = 0;

    int total_boards = (1 << n);

    for (int mask = 0; mask < total_boards; mask++) {
        int m_count = 0;
        int o_count = 0;

        for (int i = 1; i <= n; i++) {
            if (mask & (1 << (i - 1))) {
                m_positions[++m_count] = i;
            }
            else {
                o_positions[++o_count] = i;
            }
        }

        int score = 0;

        for (int i = 1; i <= m_count; i++) {
            int x = m_positions[i];

            for (int j = 1; j <= o_count; j++) {
                for (int l = j + 1; l <= o_count; l++) {
                    int y = o_positions[j];
                    int z = o_positions[l];

                    score += moove_count[x][y][z];
                }
            }
        }

        if (score > maximum_score) {
            maximum_score = score;
            board_count = 1;
        }
        else if (score == maximum_score) {
            board_count++;
        }
    }

    cout << maximum_score << " " << board_count << "\n";
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;

    while (t--) {
        solve();
    }

    return 0;
}