CF 102920B - Commemorative Dice

Rating: -
Tags: -
Solve time: 41s
Verified: yes

Solution

Problem Understanding

We are given two cubes, each with six faces. Every face contains a positive integer, and for each cube the six values sum to 21. When the cube is rolled, each face is equally likely to appear, so each cube defines a uniform probability distribution over its six face values.

The task is to compute the probability that a random roll of the first cube produces a strictly larger value than a random roll of the second cube. Every face outcome is equally likely, so this becomes a comparison over 36 equally likely ordered pairs of face values, one chosen from the first cube and one from the second.

The output must be an irreducible fraction. This means we count how many of the 36 pairs satisfy the condition “first value is greater than second value”, and then divide by 36, simplifying the fraction by dividing numerator and denominator by their greatest common divisor.

The constraints are small and fixed. Each input line contains exactly six integers, so any algorithm that is even quadratic over 6 is effectively constant time. The only meaningful consideration is correctness of probability counting and careful handling of duplicates in values, since repeated numbers affect multiplicities in the comparison.

A subtle case arises when many faces have identical values. For example, if both dice have all faces equal to 3, every outcome ties, so the answer must be 0/1. A naive approach that compares only unique values or assumes permutations would fail here, because multiplicity is essential.

Another edge situation is when values are heavily skewed, such as one die being mostly small values and the other mostly large values. In such cases, counting only distinct comparisons without frequency expansion would underestimate or overestimate probabilities.

Approaches

The most direct way to think about the problem is to simulate all possible rolls. Each die has six faces, so we can iterate over all 36 ordered pairs. For each pair, we check whether the first value is greater than the second and count how many times this happens. This is already extremely small, since 36 comparisons is constant work.

This brute-force method is correct because the dice are uniform and independent, so every pair of faces is equally likely with probability 1/36. The probability we want is exactly the fraction of favorable pairs over all pairs.

There is no real need to optimize beyond this, but the conceptual structure generalizes: if dice had many faces or were weighted, we would still rely on counting pairwise comparisons, possibly with frequency maps instead of raw enumeration.

The key observation is that the problem reduces to a discrete probability over a Cartesian product. Once that is recognized, the solution becomes a straightforward counting task rather than any combinatorial reasoning.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Pair Enumeration	O(36)	O(1)	Accepted
Frequency-based Counting (optional generalization)	O(6²)	O(1)	Accepted

Algorithm Walkthrough

Read the six values of the first die and the six values of the second die. These represent uniform probability distributions over their faces.
Initialize a counter for successful outcomes, meaning cases where a face from the first die is strictly greater than a face from the second die.
Iterate over each value in the first die.
For each such value, iterate over each value in the second die.
Compare the two values. If the first value is larger, increment the success counter.
After all pairs are processed, the total number of outcomes is fixed at 36, since there are six choices for each die.
Form the fraction success / 36.
Reduce the fraction by dividing numerator and denominator by their greatest common divisor.

Why it works

Every face on each die is equally likely, and the dice are independent. This implies each ordered pair of faces occurs with equal probability 1/36. The algorithm explicitly enumerates all such equally likely outcomes and counts exactly the favorable subset. Because no pair is omitted or weighted incorrectly, the computed ratio matches the true probability. Reduction by gcd preserves equivalence of the fraction without changing its value.

Python Solution

import sys
input = sys.stdin.readline
from math import gcd

a = list(map(int, input().split()))
b = list(map(int, input().split()))

win = 0
for x in a:
    for y in b:
        if x > y:
            win += 1

total = 36
g = gcd(win, total)

print(f"{win // g}/{total // g}")

The code directly implements the pair enumeration described earlier. The nested loops reflect the Cartesian product of faces. Since both dice always have exactly six values, we can safely hardcode the total number of outcomes as 36.

The gcd reduction ensures the output is in irreducible form, as required. There is no need for floating point arithmetic, which avoids precision issues entirely.

Worked Examples

Sample 1

Input:

First die: 3 4 3 4 3 4

Second die: 1 1 1 1 8 9

We enumerate contributions by grouping:

First value	Second values	Wins
3	1,1,1,1,8,9	4
4	1,1,1,1,8,9	4
3	same as above	4
4	same as above	4
3	same as above	4
4	same as above	4

Total wins = 24 out of 36.

win	total	fraction
24	36	2/3

This confirms that multiplicity of values directly affects probability.

Sample 2

Input:

First die: 1 2 3 4 5 6

Second die: 3 4 3 4 3 4

We compute comparisons:

First value	Wins against second die
1	0
2	0
3	beats 3s? 0, beats 4s? 0 → 0
4	beats 3s only → 3
5	beats all → 6
6	beats all → 6

Accounting for frequencies of second die values, total wins = 15 out of 36.

Simplified fraction is 5/12.

This example shows that even symmetric-looking dice can produce non-trivial probabilities due to repeated values.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(36)	fixed nested loops over six faces each
Space	O(1)	only stores input arrays and counters

The computation is constant time regardless of input distribution. This easily satisfies any reasonable limits, including strict 0.5 second constraints.

Test Cases

import sys, io
from math import gcd

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    win = 0
    for x in a:
        for y in b:
            if x > y:
                win += 1
    g = gcd(win, 36)
    return f"{win//g}/{36//g}"

# provided samples
assert run("3 4 3 4 3 4\n1 1 1 1 8 9\n") == "2/3"
assert run("1 2 3 4 5 6\n3 4 3 4 3 4\n") == "5/12"
assert run("1 2 3 4 5 6\n8 7 2 2 1 1\n") == "1/2"

# custom cases
assert run("1 1 1 1 1 1\n1 1 1 1 1 1\n") == "0/1", "all equal ties"
assert run("6 6 6 6 6 6\n1 1 1 1 1 1\n") == "1/1", "always win"
assert run("1 1 1 1 1 6\n6 6 6 6 6 1\n") == "25/36", "mixed extremes"

Test input	Expected output	What it validates
all equal dice	0/1	full tie handling
max vs min dice	1/1	dominance case
skewed mixed dice	25/36	frequency sensitivity

Edge Cases

A fully uniform case like 1 1 1 1 1 1 against itself produces zero winning pairs. The algorithm still iterates over all 36 pairs, but every comparison fails, leaving win = 0. After reduction, 0/36 simplifies correctly to 0/1.

A dominance case such as 6 6 6 6 6 6 versus 1 1 1 1 1 1 produces win = 36. The gcd with 36 is 36, and the result simplifies to 1/1, reflecting certainty.

A mixed distribution like 1 1 1 1 1 6 against 6 6 6 6 6 1 ensures that both winning and losing outcomes appear. The algorithm correctly counts frequency-weighted comparisons through raw enumeration, producing the exact probability without needing any symbolic reasoning.