TopCoder problem "RandomApple" used in Member SRM 478 (Division I Level Three)



Problem Statement

    Taro likes apples very much. He has N boxes numbered from 0 to N-1. There are K different types of apples numbered from 0 to K-1. You are given three String[]s, hundred, ten and one. Concatenate j-th characters in hundred[i], ten[i] and one[i] in this order to get a string that represents the number of j-th type apples in Box i (it may have leading zero(s)). This number will be between 0 and 199, inclusive.



He decided to choose one apple from his boxes, and he does so in the following way:

  • First Step: He chooses a non-empty subset of his N boxes randomly and transfers all apples from those boxes to another box (this is a box other than the original N boxes and it is initially empty). Each non-empty subset of boxes has the same probability of being chosen.

  • Second Step: He chooses one apple from the new box randomly. Each apple in the box has the same probability of being chosen.


Return a double[] that contains exactly K elements and whose i-th element is the probability that Taro chooses an i-th type apple.



 

Definition

    
Class:RandomApple
Method:theProbability
Parameters:String[], String[], String[]
Returns:double[]
Method signature:double[] theProbability(String[] hundred, String[] ten, String[] one)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-N will be between 1 and 50, where N is the number of elements in hundred.
-K will be between 1 and 50, where K is the number of characters in hundred[0].
-ten and one will contain exactly N elements.
-Each element in hundred, ten and one will contain exactly K characters.
-Each character in hundred will be '0' or '1'.
-Each character in ten and one will be a digit ('0'-'9').
-Each box will contain at least one apple.
 

Examples

0)
    
{"00"}
{"00"}
{"58"}
Returns: {0.38461538461538464, 0.6153846153846154 }
There is only one box which contains 5 type-0 apples and 8 type-1 apples. The probability of choosing a type-0 apple is 5 / 13.
1)
    
{"00", "00"}
{"00", "00"}
{"21", "11"}
Returns: {0.5888888888888889, 0.4111111111111111 }
If he chooses only box 0 in the first step, the probability of choosing a type-0 apple is 2 / 3.

If he chooses only box 1 in the first step, the probability of choosing a type-0 apple is 1 / 2.

If he chooses both boxes in the first step, the probability of choosing a type-0 apple is 3 / 5.



So the probability of choosing a type-0 apple is (2 / 3 + 1 / 2 + 3 / 5) / 3 = 53 / 90.
2)
    
{"0000", "0000", "0000"}
{"2284", "0966", "9334"}
{"1090", "3942", "4336"}
Returns: 
{0.19685958571981937, 0.24397246802233483, 0.31496640865458775, 0.24420153760325805 }
3)
    
{"01010110", "00011000", "00001000", "10001010", "10111110"}
{"22218214", "32244284", "68402430", "18140323", "29043145"}
{"87688689", "36101317", "69474068", "29337374", "87255881"}
Returns: 
{0.11930766223754977, 0.14033271060661345, 0.0652282589028571, 0.14448118133046356, 0.1981894622733832, 0.10743462836879789, 0.16411823601857622, 0.06090786026175882 }
4)
    
{"10"}
{"00"}
{"00"}
Returns: {1.0, 0.0 }
One box with 100 type-0 apples and no type-1 apples.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11026

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14187&pm=11026

Writer:

rng_58

Testers:

liympanda , konqueror , ivan_metelsky , keshav_57

Problem categories:

Dynamic Programming, Math