USACO 2022 January Contest Bronze Division - Non-Transitive Dice

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Let's start with deciding whether a player wins over another player. If we have two sets of four dices, we can assume that each possible roll is equally likely to show up so therefore, we have 16 equally probable outcomes, starting from the first dice roll for both of them and going all the way until the fourth roll for both of them.

Then, another key idea is observing that the numbers on dices must be at most 10, we have at most 10^4 configurations for C's dice rolls, so now we can try each one of them against A and B and see if the transitivity applies according to the statement rules (each player wins exactly one game).

A key observation is that it doesn't have to be A winning against B, B winning against C and C winning against A. It can also be A->C, C->B, B->A for example.

Therefore, we only have to see if there is at least one configuration which ensures this property, and in that case we would print yes. Otherwise, we print no.

The time complexity would be $O(10^4 * 16 * 9)$.

Source codes

The source codes in C++ and Python can be seen below.

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

int winner (vector<int> &a, vector<int> &b) {
    int delta = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (a[i] > b[j]) {
                delta++;
            }
            if (a[i] < b[j]) {
                delta--;
            }
        }
    }
    if (delta > 0) {
        return 0;
    }
    if (delta == 0) {
        return 1;
    }
    return 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for (; t; t--) {
        vector<int> a(4), b(4), c(4);
        for (int i = 0; i < 4; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < 4; i++) {
            cin >> b[i];
        }
        bool good = 0;
        for (int v0 = 1; v0 <= 10; v0++) {
            c[0] = v0;
            for (int v1 = 1; v1 <= 10; v1++) {
                c[1] = v1;
                for (int v2 = 1; v2 <= 10; v2++) {
                    c[2] = v2;
                    for (int v3 = 1; v3 <= 10; v3++) {
                        c[3] = v3;
                        vector<vector<int>> vp = {a, b, c};
                        vector<int> wins = {0, 0, 0};
                        for (int p = 0; p < 3; p++) {
                            for (int p2 = p+1; p2 < 3; p2++) {
                                int score = winner(vp[p], vp[p2]);
                                if (score == 0) {
                                    wins[p]++;
                                }
                                if (score == 2) {
                                    wins[p2]++;
                                }
                            }
                        }
                        if (wins[0] == 1 && wins[1] == 1 && wins[2] == 1) {
                            good = 1;
                            v0 = v1 = v2 = v3 = 11;
                        }
                    }
                }
            }
        }
        if (good == 0) {
            cout << "no" << '\n';
        }
        else {
            cout << "yes" << '\n';
        }
    }
    return 0;
}

def winner(a, b):
    cntA = 0
    cntB = 0
    for i in range(0, 4):
        for j in range(0, 4):
            if a[i] > b[j]:
                cntA += 1
            if a[i] < b[j]:
                cntB += 1
    if cntA > cntB:
        return 0
    if cntA == cntB:
        return 1
    if cntA < cntB: 
        return 2

t = int(input())

for _ in range(t):
    ab = list(map(int, input().split()))
    a = [ab[0], ab[1], ab[2], ab[3]]
    b = [ab[4], ab[5], ab[6], ab[7]]
    c = [0] * 4

    ok = 0
    for first in range(1, 11):
        c[0] = first
        for second in range(1, 11):
            c[1] = second
            for third in range(1, 11):
                c[2] = third
                for fourth in range (1, 11):
                    c[3] = fourth
                    players = [a, b, c]
                    cntwins = [0] * 3
                    for i in range(0, 3):
                        for j in range (i+1, 3):
                            who = winner(players[i], players[j])
                            if who == 0:
                                cntwins[i] += 1
                            if who == 2:
                                cntwins[j] += 1
                    if cntwins[0] == 1 and cntwins[1] == 1 and cntwins[2] == 1:
                        ok = 1
                        first = second = third = fourth = 11

    if ok == 1:
        print("yes")
    else:
        print("no")