USACO 2025 US Open Contest Bronze Division - Hoof Paper Scissors Minus One

Problem link: TBA

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given the relative small size of the input, we can think at a solution where for each pair Elsie chooses to play, we can try every symbol Bessie can use and see whether it's useful in any way for her to defeat Elsie no matter what.

After finding the number of symbols Bessie can use to defeat Elsie no matter what, the problem reduces to finding how many ways are there to place at least one of the symbols as one of the symbols from the pairs. This can be relatively difficult to compute, but it's easier to compute the number of pairs such that none of the symbols is a guaranteed winning symbol.

Therefore, the formula will be \(N^2 - winboth^2\), where \(winboth\) is the number of symbols Bessie can use to defeat Elsie no matter what.

Source code

The source code in C++ can be seen below.

#include <iostream>
#include <vector>

using namespace std;

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

    vector<vector<char>> win(n+1, vector<char>(n+1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> win[i][j];
        }
    }

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        int winboth = 0;
        for (int j = 1; j <= n; j++) { // symbol we iterate over
            bool scoreA = 0;
            bool scoreB = 0;
            // compute whether j wins against x or not
            if (j > x) {
                scoreA = (win[j][x] == 'W');
            }
            else {
                scoreA = (win[x][j] == 'L');
            }
            // compute whether j wins against y or not
            if (j > y) {
                scoreB = (win[j][y] == 'W');
            }
            else {
                scoreB = (win[y][j] == 'L');
            }
            if (scoreA && scoreB) { // if both win, increment the count
                winboth++;
            }
        }
        // complementary counting - subtract from every possible answer, those where Bessie can't defeat Elsie no matter what
        cout << 1LL * n * n - (n - winboth) * (n - winboth) << '\n';
    }
}

int main() {

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

    int t = 1;

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