Connection Status:
Competition Arena > CoinReversing

CoinReversing

SRM 518 · 2011-05-25 · by omeometo

SRM 518 · 2011-05-25 · by omeometo · Dynamic Programming, Simple Math
Class Name: CoinReversing
Return Type: double
Method Name: expectedHeads
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

You initially have N coins on the table, all with heads up. Given int[] a containing K integers, you first randomly choose a[0] coins and reverse them (from head to tail, or from tail to head), then randomly choose a[1] coins and reverse them, ..., and finally randomly choose a[K-1] coins and reverse them. Calculate and return the expected number of heads after these operations.

Notes

  • When you choose a specified number (say x) of coins, each combination of x coins has the same probability of being chosen.
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • N will be between 1 and 1000, inclusive.
  • a will contain between 1 and 50 elements, inclusive.
  • Each element in a will be between 1 and N, inclusive.
Examples
0)
3
{2,2}
Returns: 1.6666666666666667

You first reverse 2 coins from heads to tails. Then you randomly choose 2 coins and reverse them. There are two possible situations that can occur on the second operation: Choosing 2 tails (which occurs with probability 1/3): it results in 3 heads. Choosing 1 head and 1 tail (which occurs with probability 2/3): it results in 1 head. So the expected number of heads is 1/3*3+2/3*1=5/3.

1)
10
{10,10,10}
Returns: 0.0

You reverse every coin three times, so after the operations there will be 10 tails and no heads.

2)
10
{2,7,1,8,2,8}
Returns: 4.792639999999999
3)
1000
{916,153,357,729,183,848,61,672,295,936}
Returns: 498.1980774932278
4)
50
{50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}
Returns: 50.0

Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CoinReversing with a public method double expectedHeads(int N, vector<int> a) · 110 test cases · 2 s / 256 MB per case

Submitting as anonymous