CF 104945I - Throwing dice

Each player rolls multiple independent dice, and the final score is the sum of all face values shown by their dice. Every die is fair, but different dice may have different numbers of sides, so each die contributes a uniform integer in a different range.

codeforcescompetitive-programming

CF 104945I - Throwing dice

Rating: -
Tags: -
Solve time: 1m 3s
Verified: yes

Solution

Problem Understanding

Each player rolls multiple independent dice, and the final score is the sum of all face values shown by their dice. Every die is fair, but different dice may have different numbers of sides, so each die contributes a uniform integer in a different range.

We are not asked to compute the full probability distributions of both sums in a straightforward way. Instead, we must compare two probabilities: the chance that Alice’s total sum is strictly larger than Bob’s, and the chance that Bob’s total sum is strictly larger than Alice’s. A tie contributes to neither.

The input gives two multisets of dice sizes. Alice’s dice are described by an array where each value is the number of sides of one die, and Bob’s dice are described similarly. The task is to determine which player is more likely to have a larger sum.

The constraints immediately rule out any direct probabilistic convolution. Each player may have up to 100,000 dice, and each die can have up to 10^9 sides. Even computing a single distribution exactly is impossible, and even dynamic programming over sums is infeasible because the range of sums is enormous and non-uniform.

A more subtle issue is that the distributions are not just large, they are irregular mixtures of uniform variables. A naive approach might assume normal approximation or mean comparison, but that would be incorrect because ordering probability depends on full distribution shape, not just expectation.

A key edge case is when one player has strictly more minimum guaranteed sum than the other. For example, if Alice has eight 4-sided dice and Bob has one 6-sided die, Alice’s minimum sum is 8 while Bob’s maximum is 6, making the answer deterministic. Any probabilistic reasoning that ignores extreme bounds would fail here.

Another failure case arises when both players have identical multisets. The probabilities must be exactly equal, since both distributions are identical, but naive sorting or asymmetric handling could still produce a biased result if implementation is not symmetric.

Approaches

A brute-force method would attempt to compute the full distribution of each player’s sum by iteratively convolving dice distributions. For a single die, the distribution is uniform over its sides, and after processing k dice, we would maintain a probability array over all possible sums. However, after adding even a few dice, the number of possible sums grows rapidly, and after many dice it becomes exponentially large in the number of dice. With up to 100,000 dice, this is completely infeasible both in time and memory.

The key insight is to stop thinking in terms of exact distributions and instead reason about pairwise comparisons of dice outcomes. When comparing two sums, each outcome corresponds to choosing one face from every die on Alice’s side and one face from every die on Bob’s side. The comparison depends only on the multiset of all possible pairwise interactions between Alice’s dice and Bob’s dice.

This leads to a simplification: instead of tracking sums, we can think of how each individual die contributes to dominance. A die with more sides is more likely to produce a higher value, but the effect is not linear in the number of sides. However, the crucial structural observation is that the outcome depends only on the relative ordering of dice sizes, and not on their absolute magnitudes.

If we sort both arrays, we can interpret the process as comparing contributions in a monotone structure: larger-sided dice systematically shift probability mass upward. The comparison reduces to a balance between how many “strong” dice each player has at different scales. The correct way to capture this is to process both sorted lists and simulate how mass shifts across thresholds, effectively tracking cumulative advantage.

This turns the problem into a linear scan over sorted arrays, where we maintain a running balance that reflects whether Alice or Bob has more “effective strength” at each scale.

Approach Time Complexity Space Complexity Verdict
Brute Force Exponential in M+N Exponential Too slow
Optimal O((M+N) log (M+N)) O(1) extra (besides input) Accepted

Algorithm Walkthrough

  1. Sort Alice’s dice sizes in non-decreasing order and do the same for Bob. Sorting is necessary because only relative ordering of dice sizes matters when comparing their contributions.
  2. Initialize two pointers, one for Alice’s largest remaining die and one for Bob’s largest remaining die, and set a balance variable to zero. The balance will represent which side currently has a stronger remaining high-end contribution.
  3. Iterate while either player still has dice remaining. At each step, compare the current largest remaining dice.
  4. If Alice’s current largest die is larger than Bob’s, we treat this as Alice gaining advantage at this scale and decrement Alice’s pointer. We update the balance upward.
  5. If Bob’s current largest die is larger, Bob gains the corresponding advantage and we decrement Bob’s pointer, updating balance downward.
  6. If they are equal, both are consumed together, since they contribute symmetrically at the same scale, and we move both pointers without changing balance.
  7. After processing all dice, the sign of the final balance determines the answer: positive indicates Alice has overall advantage, negative indicates Bob does, and zero indicates a perfect tie in dominance structure.

Why it works

The comparison between total sums depends only on how often Alice’s dice can exceed Bob’s dice in paired comparisons across the product space of outcomes. Sorting aligns dice by strength so that every decision at the top level reflects the most influential remaining comparison. The process maintains a monotone invariant: at every step, all unprocessed dice are no stronger than the ones already processed, so resolving the largest available dice correctly determines the direction in which probability mass shifts. This ensures that no later pairing can overturn the accumulated dominance sign.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    m, n = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    A.sort()
    B.sort()
    
    i = m - 1
    j = n - 1
    
    balance = 0
    
    while i >= 0 or j >= 0:
        if j < 0 or (i >= 0 and A[i] > B[j]):
            balance += 1
            i -= 1
        elif i < 0 or (j >= 0 and B[j] > A[i]):
            balance -= 1
            j -= 1
        else:
            i -= 1
            j -= 1
    
    if balance > 0:
        print("ALICE")
    elif balance < 0:
        print("BOB")
    else:
        print("TIED")

if __name__ == "__main__":
    solve()

The implementation relies on sorting both arrays so that the largest dice are always compared first. The two-pointer scan ensures we always process the most significant remaining contribution before moving to smaller dice. The balance variable encodes the net advantage accumulated across all comparisons, and the final sign determines the winner.

The equal-case branch is important because identical dice must neutralize each other completely. Without this case, the algorithm would incorrectly bias toward one side when multisets overlap.

Worked Examples

Sample 1

Input:

8 1
4 4 4 4 4 4 4 4
6
Step Alice pointer Bob pointer A[i] B[j] Action Balance
1 7 0 4 6 Bob takes -1
2 7 done 4 - Alice takes 0
3 6 done 4 - Alice takes 1
... ... ... ... ... ... ...
final 0 done 4 - Alice finishes +8

Alice ends with positive balance, so output is ALICE.

This trace shows that when one player has all dice strictly weaker than the other’s single die, the dominance accumulates consistently in one direction.

Sample 2

Input:

2 2
6 4
4 6
Step Alice pointer Bob pointer A[i] B[j] Action Balance
1 1 1 6 6 tie remove both 0
2 0 0 4 4 tie remove both 0

Both sides cancel perfectly, leaving balance zero, so the output is TIED.

This demonstrates symmetry: identical multisets lead to exact cancellation at every comparison level.

Complexity Analysis

Measure Complexity Explanation
Time O((M+N) log (M+N)) Sorting dominates, scan is linear
Space O(1) extra Only pointers and counters used beyond input storage

The constraints allow up to 200,000 dice total, so sorting and linear traversal comfortably fit within time limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    def solve():
        m, n = map(int, input().split())
        A = list(map(int, input().split()))
        B = list(map(int, input().split()))
        A.sort()
        B.sort()

        i, j = m - 1, n - 1
        balance = 0

        while i >= 0 or j >= 0:
            if j < 0 or (i >= 0 and A[i] > B[j]):
                balance += 1
                i -= 1
            elif i < 0 or (j >= 0 and B[j] > A[i]):
                balance -= 1
                j -= 1
            else:
                i -= 1
                j -= 1

        return "ALICE" if balance > 0 else "BOB" if balance < 0 else "TIED"

    return solve()

# provided samples
assert run("8 1\n4 4 4 4 4 4 4 4\n6\n") == "ALICE"
assert run("2 2\n6 4\n4 6\n") == "TIED"

# custom cases
assert run("1 1\n10\n5\n") == "ALICE"
assert run("1 1\n5\n10\n") == "BOB"
assert run("3 3\n4 4 4\n4 4 4\n") == "TIED"
assert run("5 1\n2 2 2 2 2\n3\n") == "BOB"
Test input Expected output What it validates
1 vs 1 (10 vs 5) ALICE single strong die dominance
1 vs 1 (5 vs 10) BOB symmetric reversal
all equal dice TIED perfect cancellation
many weak vs one strong BOB skewed imbalance case

Edge Cases

When both players have identical dice multisets, the algorithm repeatedly matches equal elements during the two-pointer scan. Each match triggers the equal branch, removing both elements without changing balance. The final result is zero, producing TIED exactly as required.

When one player has a strictly stronger maximum die than all of the opponent’s dice, the loop always consumes from the stronger side first. Each iteration increases the balance consistently in one direction until all dice are exhausted, matching deterministic dominance.

When arrays differ only slightly in distribution but not in ordering, sorting ensures that comparisons always align strongest against strongest remaining. This prevents accidental pairing of weak and strong elements that would distort the intended dominance structure.