1418. The Expected Value of a Weighted Draw

A bag holds tickets. For each of n kinds there are w[i] tickets, every one of them carrying the value v[i]. One ticket is drawn uniformly at random. Print the expected value of the number on it, as an exact reduced fraction.

n = 3, (v, w) = (1,1) (2,1) (3,1) three equally likely values, so the expectation is (1 + 2 + 3)/3 = 2/1

Values may be negative. Weights are at least 1, so the bag is never empty.

## The sign rule, pinned before anything is asserted

A fraction has more than one reduced spelling unless the sign is placed by a rule: -1/2 and 1/-2 are the same number. So this problem requires

• the denominator positive,
• the sign carried by the numerator,
• zero written exactly 0/1.

Without that sentence the five reference languages would disagree and the problem would be unanswerable rather than hard.

## What most people try first

Sum v[i] * w[i] / W in floating point, where W is the total weight. The expectation is almost never exactly representable in binary, so the printed digits depend on the rounding mode and the order of the additions, and the five reference languages would not agree. The fix is not more digits, it is not dividing at all until the very end.

The second attempt divides each term first: v[i] * (w[i] / W) in integers, where w[i] / W is 0 for every term. The expectation then comes out 0.

## One fraction, formed once

numerator = v[0]*w[0] + v[1]*w[1] + ... + v[n-1]*w[n-1] denominator = w[0] + w[1] + ... + w[n-1]

and then one reduction by the gcd. No division happens before that.

## Why it is correct

The probability of drawing a ticket of kind i is w[i] / W, since the tickets are equally likely and w[i] of them are of that kind. By the definition of expectation,

E = sum over i of v[i] * (w[i] / W) = (sum over i of v[i] * w[i]) / W

because every term shares the denominator W, so it factors out. That single step is the whole content of the problem, and it is what makes the exact answer available: a sum of integers over an integer.

## The boundary that breaks a careless implementation

Reducing is not optional cosmetics, it is what makes the answer unique. Both 2/1 and 4/2 describe the same expectation, and only one of them is the required output. The sign rule then settles the rest: a negative expectation prints its sign on the numerator, and an expectation of exactly zero prints 0/1, which comes out of gcd(0, W) = W without a special case.

## Overflow

|v[i]| reaches 10^9 and w[i] reaches 10^6, so each product reaches 10^15 and the running numerator over 1000 draws reaches 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, and does not fit a signed 32-bit one, whose limit is 2147483647: a 32-bit build answers -23913984/15625 for a single draw whose true expectation is 1000000000/1. The denominator reaches 10^9, which does fit 32 bits, since 2 * 10^9 is still inside 2147483647; it is the numerator that forces the width. In JavaScript 10^18 is past 2^53, so BigInt is required.

## Cost

O(n + log W).

Constraints - `1 ≤ n ≤ 1000` - `-1000000000 ≤ v[i] ≤ 1000000000` - `1 ≤ w[i] ≤ 1000000`