SeeAllDifferences
SRM 824 · 2022-02-17 · by misof
Problem Statement
Misko and Danka are playing with a D-sided die. The die has faces numbered from 1 to D and it is a fair die: whenever rolled, each number will come up with probability 1 / D.
In their current game Misko is repeatedly rolling the die and Danka is taking notes as follows: After the very first roll, she does nothing. After each of the following rolls, she writes down the (non-negative) difference between the current and the previous outcome.
You are given the
Misko knows that Danka will not be happy until she has seen each possible difference occur at least once. He now wonders how many additional rolls this will take. Calculate and return the expected number of extra rolls needed until Danka will be happy.
Notes
- Your answer will be accepted if it has an absolute or a relative error at most 10^(-9).
Constraints
- D will be between 2 and 16, inclusive.
- rolled will contain between 1 and 50 elements, inclusive.
- Each element of rolled will be between 1 and D, inclusive.
2
{1,2,1}
Returns: 2.0
The kids have a 2-sided die, i.e., a coin with sides labelled 1 and 2. Misko already tossed the coin three times. Danka has already written down the difference 1 twice. In order for Danka to be happy, she also needs to see the difference 0. In each of the following coin tosses this will happen with probability 1/2. From this, we can show that the expected number of coin tosses until it happens is 1 / (1/2) = 2.
6
{3, 3, 4, 6, 1, 5, 2, 3, 4, 2, 2, 6}
Returns: 0.0
Danka has already been happy for a while: here, the first six differences have already all been distinct.
4
{2}
Returns: 11.896969696969695
6
{1}
Returns: 23.771221030410732
6
{2}
Returns: 25.271382862323605
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SeeAllDifferences with a public method double solve(int D, vector<int> rolled) · 128 test cases · 2 s / 256 MB per case