Connection Status:
Competition Arena > RiggedLottery

RiggedLottery

2016 TCO Russia Regional · 2016-03-24 · by ffao

2016 TCO Russia Regional · 2016-03-24 · by ffao · Dynamic Programming, Math
Class Name: RiggedLottery
Return Type: int
Method Name: getProbability
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

In a traditional lottery, the players are trying to guess a set of K numbers that is selected at random. The K numbers are distinct and each of them is between 0 and N-1, inclusive. Usually, the chances of winning in such a lottery are very small. However, it has come to your attention that your local lottery may be biased. You now want to analyze this bias.


Your source has sent you pseudocode of the algorithm used by your local lottery. The pseudocode is shown below. The values returned by the function random() are mutually independent.


def random(P):
    generate and return a random value between 0 and N-1, inclusive,
    in such a way that the probability of returning value i is P[i] / 1000

def lottery(K,P):
    selected_numbers = an empty set
    while selected_numbers has fewer than K elements:
        candidate = random(P)
        if candidate is not in selected_numbers:
             add candidate to selected_numbers
    return selected_numbers

You are given the int K and the int[] P: the probability distribution used in the pseudocode. Your favorite number is the number 0. You would like to compute the probability that this number will be among the K selected numbers. This probability can be expressed as an irreducible fraction Q / R. It can be shown that under the constraints of this problem there exists exactly one integer Y between 0 and 10^9+6, inclusive, that satisfies the modular equation R * Y = Q (mod 10^9+7). Return the value of Y.

Constraints

  • N will be between 1 and 50, inclusive.
  • K will be between 1 and N, inclusive.
  • P will contain exactly N elements.
  • Each element in P will be between 1 and 1000, inclusive.
  • The sum of all elements of P will be 1000.
Examples
0)
1
{300,250,450}
Returns: 100000001

In this lottery we are selecting one number from the set {0,1,2}. The number 0 is selected with the probability 300/1000. The corresponding irreducible fraction is 3/10. The correct return value is 100000001 because 10 * 100000001 = 3 (mod 10^9+7).

1)
2
{200,600,200}
Returns: 350000003

The probability that 0 is the first number added to selected_numbers is obviously 0.2. It can be computed that the probability that 0 is the second number added to selected_numbers is 0.35. As these two options are mutually exclusive, the total probability that 0 is selected is 0.55 = 11/20. We have 20 * 350000003 = 11 (mod 10^9+7).

2)
3
{100, 500, 400}
Returns: 1
3)
4
{30,799,92,66,13}
Returns: 233159814
4)
24
{13,8,49,2,12,69,30,22,21,48,18,8,37,30,13,10,12,30,15,63,33,38,46,10,93,52,26,11,13,14,19,48,1,9,5,31,7,4,10,20}
Returns: 959464924

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

Coding Area

Language: C++17 · define a public class RiggedLottery with a public method int getProbability(int K, vector<int> P) · 52 test cases · 2 s / 256 MB per case

Submitting as anonymous