RandomPancakeStack
SRM 656 · 2015-03-26 · by lg5293
Problem Statement
Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].
Charlie chooses the pancakes he is going to serve using the following randomized process: He starts by choosing the first pancake uniformly at random from all the pancakes he has. He places the chosen pancake onto a plate. This pancake now forms the bottom of a future stack of pancakes. Then, Charlie repeats the following procedure:
- If there are no more pancakes remaining, terminate.
- Choose a pancake uniformly at random from the pancakes that have not been chosen yet.
- If the width of this pancake is greater than the width of the pancake on top of the stack, terminate without taking it.
- Place the chosen pancake on top of the stack and go back to step 1.
You are given the
Notes
- Your return value must have an absolute or relative error smaller than or equal to 1e-6
Constraints
- The number of elements in d will be between 1 and 250, inclusive.
- Each element of d will be between 1 and 1,000, inclusive.
{1,1,1}
Returns: 1.6666666666666667
The following scenarios may occur: With probability 1/3, Charlie chooses pancake 0 first. In this case he won't be able to add any more pancakes and the total deliciousness of his serving of pancakes will be 1. With probability 1/3, Charlie chooses pancake 1 first. What happens in the second round? With probability 1/2 he will choose pancake 0 and with probability 1/2 it will be pancake 2. In the first case the total deliciousness of Charlie's pancakes will be 2, in the second case it will be 1. With probability 1/3, Charlie chooses pancake 2 first. If he chooses pancake 0 next, the total deliciousness of his pancakes will be 2. If he happens to choose pancake 1 next (followed by pancake 0 in the third round), the total deliciousness will be 3. Summing this up, we get the expected deliciousness to be 1/3 * (1) + 1/3 * (1/2 * 1 + 1/2 * 2) + 1/3 * (1/2 * 2 + 1/2 * 3) = 5/3 = 1.666...
{3,6,10,9,2}
Returns: 9.891666666666667
{10,9,8,7,6,5,4,3,2,1}
Returns: 10.999999724426809
{1,2,3,4,5,6,7,8,9,10}
Returns: 7.901100088183421
{2,7,1,8,2,8,1,8,2,8,4,5,90,4,5,2,3,5,60,2,8,74,7,1}
Returns: 19.368705050402465
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomPancakeStack with a public method double expectedDeliciousness(vector<int> d) · 74 test cases · 2 s / 256 MB per case