DistinctFaces
SRM 838 · 2022-09-19 · by misof
Problem Statement
You have a collection of dice: for each valid index i you have exactly count[i] dice with size[i] faces.
A die with x faces has them labelled with integers from 1 to x, inclusive. When such a die is rolled, one of those integers is selected uniformly at random. All dice rolls are mutually independent.
If you roll your entire collection, what is the expected number of distinct values you'll see?
The answer can always be expressed as a reduced fraction A/B, where both numbers are coprime with M = 10^9 + 7. Let B^(-1) denote the inverse of B when computing modulo M. Calculate and return (A * B^(-1)) mod M.
Constraints
- count will have between 1 and 50 elements, inclusive.
- size will have the same number of elements as count.
- Each element of count will be between 1 and 10^6, inclusive.
- Each element of size will be between 1 and 10^6, inclusive.
- The elements of size will be distinct.
{1}
{47}
Returns: 1
This is easy: you roll the only die you have and you are guaranteed to see exactly one value.
{2}
{6}
Returns: 833333341
Two six-sided dice. With probability 1/6 you roll doubles and then you'll see only one distinct value. With probability 5/6 you'll see two distinct values. The expected number of distinct values you'll see is therefore (1/6 * 1 + 5/6 * 2) = 11/6 = 1.833333. Computing modulo M = 10^9 + 7, the modular inverse of 6 is 166,666,668. Thus, we should return (11 * 166,666,668) mod M = 833,333,341.
{1, 1}
{1, 100}
Returns: 430000005
Again we have two dice but now they are distinct: one has only one face (and thus always rolls a 1), the other has 100 faces. Rolling two 1s is pretty unlikely and thus the expected number of distinct values is almost equal to 2. The exact value is 199/100. The answer is computed as (199 * 100^(-1)) mod M = (199 * 570,000,004) mod M = 430,000,005.
{48}
{6}
Returns: 368315208
{1000}
{2}
Returns: 272979609
One thousand fair coins.
{2, 1, 1}
{6, 10, 20}
Returns: 497500007
A set of common Dungeons&Dragons dice: two d6s, a d10 and a d20. We can iterate over all 6*6*10*20 equally likely outcomes to calculate the exact expected number of distinct values. The result is 25326 / 7200 = 1407 / 400 = 3.5175. Our return value is (1407 * 400^(-1)) mod M = 497,500,007.
Submissions are judged against all 73 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DistinctFaces with a public method int expectation(vector<int> count, vector<int> size) · 73 test cases · 2 s / 256 MB per case