Table of Contents

ExplanationImplementation

Official Analysis (C++, Java, Python)

Explanation

To begin with this problem, we must first understand what it means for three dice to be transitive. Dice are transitive when dice AA beats dice BB, dice BB beats dice CC, and dice CC beats dice AA. Dice AA beats dice BB when there are more pairs (x,y)(x, y) where xx is a side of dice AA and yy is a side on dice BB where x>yx > y compared to when y<xy < x.

Since each dice has four sides and there are ten possible values for each side, there are 104=10,00010^4 = 10,000 possible dice to test. This number is small enough that we can test every possible dice for non-transitivity via brute force.

Implementation

Time Complexity: O(1)\mathcal{O}(1) for each test case

C++

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


using Die = array<int, 4>;


/** @return whether dice A beats dice B */
bool beats(const Die &a, const Die &b) {
	int wins = 0, losses = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class NonTransitiveDice {
	/** @return whether dice A beats dice B */
	static boolean beats(int[] dice1, int[] dice2) {
		int diff = 0;
		for (int x : dice1) {

Python

def win(a: list[int], b: list[int]) -> bool:
	""":return: whether dice A beats dice B."""
	return sum([x > y for x in a for y in b]) > sum([y > x for x in a for y in b])




for _ in range(int(input)):
	l = [int(x) for x in input().split()]
	a_die = l[0:4]
	b_die = l[4:8]

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum