RollAllOnes
SRM 825 · 2022-03-07 · by misof
Problem Statement
You have a collection of N dice. Each die has D faces. The faces of each die are numbered from 1 to D. All dice are fair: whenever rolled, each of the numbers will come up with probability 1 / D.
In the beginning, all dice are placed on the table so that each of them shows the number D. Your goal is to create a state in which all your dice show the number 1 instead.
You are going to reach the goal via a sequence of actions. In each action you can select an arbitrary subset of dice (regardless of what number they currently show), pick them up and reroll them. Each such action counts as one additional roll, regardless of how many dice you rerolled.
You are trying to minimize the expected number of rolls needed to reach the given goal. Assuming you are using the best possible strategy, what is this expected number of rolls? Calculate and return it.
Notes
- Your answer will be accepted if it has a relative error at most 10^(-9).
- Each time you roll some dice, the new value visible on each die is chosen uniformly at random. All these random choices are mutually independent.
Constraints
- N will be between 1 and 50, inclusive.
- D will be between 2 and 20, inclusive.
1 6 Returns: 6.000000000000002
You have a single six-sided die. The best you can do is reroll it until you get a 1. As in each roll this has a probability p = 1/6 of happening, the expected number of attempts until it happens is 1/p = 6.
2 2 Returns: 2.6666666666666665
Two coins, each with the number 1 on one side and the number 2 on the other side.
3 10 Returns: 17.900563216158464
Three 10-sided dice.
1 2 Returns: 2.0
1 20 Returns: 19.999999999999982
Submissions are judged against all 17 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RollAllOnes with a public method double solve(int N, int D) · 17 test cases · 2 s / 256 MB per case