Connection Status:
Competition Arena > RandomApple

RandomApple

Member SRM 478 · 2009-12-03 · by rng_58

Member SRM 478 · 2009-12-03 · by rng_58 · Dynamic Programming, Math
Class Name: RandomApple
Return Type: double[]
Method Name: theProbability
Arg Types: (vector<string>, vector<string>, vector<string>)
Problem Statement

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.

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.

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

Coding Area

Language: C++17 · define a public class RandomApple with a public method vector<double> theProbability(vector<string> hundred, vector<string> ten, vector<string> one) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous