USACO 2025 Hoof Paper Scissors Minus One: Case Analysis and Counting

USACO problems that involve games often tempt students to simulate every possible match directly. That can become messy. Hoof Paper Scissors Minus One is a useful teaching problem because it shows how to replace repeated simulation with a table of relationships and a counting formula.

Represent the game as a relationship table

Instead of asking "who wins this query?" from scratch each time, store whether move a beats move b. That gives a table where each cell answers one yes-or-no question.

beats[a][b] == true  means move a beats move b

Once that table exists, each query becomes a counting problem. We can scan all possible moves and count how many moves beat both moves mentioned in the query.

A tiny example

Imagine there are four possible moves: 0, 1, 2, and 3. Suppose the relationship table tells us:

• Move 3 beats move 0.
• Move 3 beats move 1.
• Move 2 beats move 1.

For a query involving moves 0 and 1, move 3 is a strong response because it beats both. Move 2 only beats one of them, so it is not counted in the "beats both" group.

From winning count to answer count

After counting the moves that beat both query moves, call that number winning. If there are N total moves, then N - winning moves are not in that strong response group.

The solution can count all ordered pairs of choices, then subtract the pairs where neither choice is strong enough:

totalPairs = N * N
badPairs = (N - winning) * (N - winning)
answer = totalPairs - badPairs

This formula is the heart of the problem. It avoids checking every pair separately for every query.

Java implementation shape

The code structure usually has two main phases:

1. Read the outcome grid and build a table where beats[a][b] is true when move a defeats move b.
2. For each query, count the moves that beat both query moves, then apply the pair-counting formula.

int winning = 0;
for (int move = 0; move < n; move++)
{
    if (beats[move][x] && beats[move][y])
    {
        winning++;
    }
}

long total = (long) n * n;
long losing = (long) (n - winning) * (n - winning);
System.out.println(total - losing);

Why long matters

Even when the individual counts fit in int, the product N * N may be large. Casting before multiplication prevents overflow:

long total = (long) n * n;

This is a common USACO habit. If the answer counts pairs, intervals, or combinations, check whether long is safer.

Common mistakes

• Reversing the relationship: beats[a][b] and beats[b][a] mean opposite things.
• Counting moves that beat either query move: this problem needs the moves that beat both.
• Forgetting ordered pairs: N * N counts ordered choices, not just combinations.
• Multiplying as int first: cast to long before the multiplication.

Practice prompt

Create a game with five move types. Write down three relationships, build a small beats table, and answer one query by hand using the formula above. Then compare your manual result with a short program.