DiceOperation
SRM 841 · 2022-11-07 · by misof
Problem Statement
We have a collection of regular dice. Different dice in this collection may have a different number of faces.
For each X, an X-sided die has faces numbered from 1 to X. When rolled, each face comes up with probability 1/X.
You are given the
We are going to roll all dice in our collection (each of them exactly once) and then we'll compute the bitwise xor of all values rolled.
Calculate and return the expected value of the result we'll obtain.
Notes
- The return value must have an absolute or a relative error at most 10^(-9).
- All dice rolls are mutually independent.
- See https://en.wikipedia.org/wiki/Expected_value if you need a definition of the expected value of a random variable.
Constraints
- dice will contain between 1 and 10 elements, inclusive.
- Each element of dice will be between 1 and 10^9, inclusive.
{1, 1, 1, 1, 1}
Returns: 1.0
Five "dice", each of them is guaranteed to roll a 1. The xor of five 1s is 1.
{1, 1, 1, 1, 1, 1}
Returns: 0.0
As above, but now the xor of six 1s is 0.
{3, 3}
Returns: 1.3333333333333335
With probability 1/3 the two values rolled are equal and thus their xor is zero. with probability 2/9 we get the values {1, 2}, their xor is 3. with probability 2/9 we get the values {1, 3}, their xor is 2. with probability 2/9 we get the values {2, 3}, their xor is 1. Thus, the expected value of the result is (1/3)*0 + (2/9)*3 + (2/9)*2 + (2/9)*1 = 4/3.
{3, 4}
Returns: 2.5
All the outcomes from the previous example are still possible but now they are somewhat less likely. Here it is also possible to roll {1,4}, {2,4}, or {3,4}, each with probability 1/12.
{5, 9, 6}
Returns: 5.277777777777778
{47}
Returns: 24.0
With a single die the final result is simply the value you rolled.
Submissions are judged against all 79 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DiceOperation with a public method double solve(vector<int> dice) · 79 test cases · 2 s / 256 MB per case