Statistics

Problem Statement for "RiggedLottery"

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.

Definition

Class:
RiggedLottery
Method:
getProbability
Parameters:
int, int[]
Returns:
int
Method signature:
int getProbability(int K, int[] P)
(be sure your method is public)

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

  1. 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).

  2. 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).

  3. 3

    {100, 500, 400}

    Returns: 1

  4. 4

    {30,799,92,66,13}

    Returns: 233159814

  5. 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

  6. 2

    {273, 11, 5, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 665, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 50522621

  7. 6

    {40,37,38,56,61,144,83,175,198,145,23}

    Returns: 284105175

  8. 15

    {63,21,118,1,33,18,97,5,68,19,3,64,24,56,41,58,28,4,130,149}

    Returns: 179709659

  9. 5

    {111,65,77,48,33,20,30,5,11,3,17,5,42,43,11,35,27,25,3,4,11,5,40,8,82,2,2,2,10,6,9,4,44,39,1,51,19,15,35}

    Returns: 270392974

  10. 23

    {98,26,25,36,75,80,73,51,42,6,84,71,52,9,3,12,10,11,103,25,9,46,53}

    Returns: 1

  11. 9

    {126,134,43,46,99,142,50,53,31,21,75,30,87,63}

    Returns: 833135327

  12. 5

    {7,56,94,5,23,131,7,9,35,93,25,42,109,33,2,19,5,20,36,26,2,48,9,51,15,98}

    Returns: 146074342

  13. 11

    {46,9,104,1,32,18,11,19,8,13,1,38,72,50,1,16,4,3,34,6,5,9,16,17,39,52,16,8,139,39,21,15,57,6,34,20,21}

    Returns: 543416178

  14. 1

    {126,268,248,144,40,174}

    Returns: 982000007

  15. 12

    {47,135,89,224,17,10,91,79,10,119,113,66}

    Returns: 1

  16. 4

    {37,15,7,14,3,19,24,89,13,64,91,52,35,17,2,3,17,17,21,37,42,22,60,12,13,12,20,3,30,38,66,20,35,13,14,23}

    Returns: 114701546

  17. 24

    {2,68,76,2,15,42,39,79,3,75,10,17,14,18,9,118,50,51,23,68,39,15,4,4,13,20,10,42,29,2,25,18}

    Returns: 142147103

  18. 2

    {5,32,1,17,345,156,11,145,63,153,72}

    Returns: 550550938

  19. 34

    {7,83,18,19,43,13,43,85,15,49,32,31,2,2,52,3,69,6,4,9,31,44,10,21,37,19,9,59,33,2,22,36,23,6,4,5,1,53}

    Returns: 865088878

  20. 23

    {33,22,11,11,97,7,10,17,2,37,47,55,68,86,35,42,6,31,29,7,7,58,26,62,27,12,3,11,60,18,25,38}

    Returns: 332047792

  21. 18

    {37,37,36,29,20,24,137,35,6,26,13,19,135,57,67,27,5,1,19,247,23}

    Returns: 168085724

  22. 1

    {542,458}

    Returns: 494000004

  23. 17

    {1,45,15,32,74,28,52,12,66,11,41,18,47,43,2,8,4,44,7,13,8,8,9,14,1,71,42,89,3,19,38,9,62,20,9,27,8}

    Returns: 679910153

  24. 10

    {31,31,27,14,49,233,31,23,43,165,14,14,66,8,47,39,43,6,3,68,45}

    Returns: 457763504

  25. 20

    {67,6,51,115,31,62,30,133,45,12,105,6,8,9,37,32,64,10,14,40,19,104}

    Returns: 894128632

  26. 1

    {1000}

    Returns: 1

  27. 43

    {1,14,5,6,28,15,8,32,11,1,81,13,18,26,13,10,39,20,9,48,18,17,13,21,71,2,21,29,6,8,32,4,36,20,26,6,31,15,19,3,4,15,27,19,24,5,31,2,58,19}

    Returns: 35262207

  28. 46

    {10,14,1,11,7,17,12,18,58,36,8,18,70,30,1,6,16,27,29,8,12,18,42,38,4,3,59,4,21,19,17,25,23,28,23,62,33,4,8,1,2,10,38,1,2,6,22,69,9}

    Returns: 219822188

  29. 41

    {10,52,11,15,25,29,8,74,2,48,9,5,11,2,20,28,3,40,7,19,10,21,11,9,2,11,24,31,11,44,18,4,6,18,3,209,49,1,2,2,12,3,1,3,14,9,18,19,16,1}

    Returns: 74482567

  30. 11

    {16,7,19,3,56,3,21,43,2,60,1,24,4,38,8,33,4,7,3,11,85,39,26,17,15,9,13,35,13,87,40,28,4,32,23,23,6,45,12,17,32,36}

    Returns: 307699393

  31. 42

    {83,2,4,12,21,7,8,2,83,4,120,21,11,19,1,46,12,34,13,10,26,8,39,2,11,19,12,4,15,7,7,2,77,20,9,12,17,45,24,27,18,16,3,8,45,5,1,8}

    Returns: 235722120

  32. 28

    {10,18,8,45,1,10,34,46,9,26,26,10,12,48,49,87,20,6,6,13,7,17,77,16,45,21,8,52,17,11,12,33,43,28,2,3,39,20,4,61}

    Returns: 358548165

  33. 9

    {9,8,55,20,10,20,3,14,1,23,45,1,76,2,13,45,4,13,4,32,114,26,22,51,2,6,7,29,29,11,22,2,76,53,22,22,57,7,32,12}

    Returns: 478968871

  34. 42

    {4,56,9,11,117,31,9,12,16,3,4,2,64,18,39,5,1,45,4,27,11,38,7,7,49,28,41,15,22,23,35,1,6,11,6,27,10,7,13,28,32,10,6,31,7,22,30}

    Returns: 128443768

  35. 37

    {18,50,15,19,8,14,2,12,4,5,40,30,15,1,27,48,9,8,9,10,8,12,51,21,8,16,9,13,48,10,40,22,5,32,3,45,9,9,15,46,2,44,93,49,29,4,3,9,1}

    Returns: 563955939

  36. 27

    {23,27,21,5,16,34,21,3,23,7,34,6,17,5,9,16,11,16,1,3,72,27,3,7,13,23,3,18,12,4,30,1,44,12,44,34,18,45,26,8,1,5,46,24,36,33,15,28,66,4}

    Returns: 214963926

  37. 12

    {10,12,84,40,19,21,11,45,9,2,31,31,30,40,15,34,30,15,19,7,32,1,23,25,33,43,33,22,41,59,1,23,28,3,5,60,32,12,14,5}

    Returns: 722179089

  38. 21

    {11,5,23,20,14,1,30,49,49,10,26,8,57,13,71,19,13,23,5,10,14,9,68,16,9,42,7,4,11,32,7,11,5,22,90,2,26,8,1,1,4,28,23,26,10,38,29}

    Returns: 512611957

  39. 34

    {19,8,21,22,13,6,5,26,31,3,66,13,29,14,21,38,11,34,34,25,4,11,3,116,16,13,8,68,80,12,39,5,54,18,7,16,52,5,4,8,5,12,5}

    Returns: 393914771

  40. 28

    {4,12,15,3,11,10,21,11,4,21,19,2,18,3,75,4,58,12,3,1,15,14,94,5,12,1,23,34,4,13,28,18,19,11,35,4,4,4,7,109,12,227}

    Returns: 931714050

  41. 46

    {11,6,22,19,16,6,2,1,1,14,16,6,25,10,18,2,4,13,10,14,10,19,5,25,13,27,8,7,14,9,11,38,12,51,38,7,9,23,11,44,26,1,72,86,66,152}

    Returns: 1

  42. 38

    {4,27,9,8,5,5,20,3,2,18,9,4,25,9,83,42,31,9,13,19,20,23,25,15,41,7,13,18,24,12,14,20,16,4,24,12,33,62,9,68,67,128}

    Returns: 219470955

  43. 16

    {230,128,108,112,117,4,83,35,61,2,5,10,11,10,13,1,17,1,6,5,7,3,2,4,2,1,1,1,1,1,3,1,1,1,1,1,2,2,1,2,1,1,1}

    Returns: 26652739

  44. 18

    {187,442,109,47,2,16,15,13,5,25,20,2,8,19,14,16,10,2,1,2,1,5,1,3,3,1,6,1,1,6,1,1,2,1,1,2,3,1,1,1,1,1,1}

    Returns: 101489484

  45. 28

    {527,13,98,63,92,2,56,11,2,19,11,7,2,1,17,5,4,6,1,1,2,1,2,3,5,14,3,2,1,6,1,1,4,3,1,1,1,2,1,1,1,1,1,1,1,1,1}

    Returns: 774928689

  46. 26

    {19,283,428,4,29,3,29,11,6,39,5,41,27,1,5,16,10,1,4,1,3,5,2,2,1,3,1,1,2,1,1,3,2,1,1,1,2,1,1,1,1,1,1}

    Returns: 278032089

  47. 50

    {7,102,25,3,16,25,15,26,3,31,6,9,39,1,6,40,24,1,12,50,19,22,19,4,11,21,18,26,69,15,11,10,1,31,18,2,24,3,23,5,23,2,33,32,37,6,26,34,2,12}

    Returns: 1

  48. 1

    {7,22,29,73,6,42,1,10,11,23,5,5,11,7,41,28,14,24,48,36,34,40,35,27,21,8,48,33,9,14,18,12,19,5,3,44,15,18,27,6,3,3,6,6,2,24,27,32,5,13}

    Returns: 999000007

  49. 49

    {951,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 113539408

  50. 49

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,951}

    Returns: 936458387

  51. 49

    {20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20}

    Returns: 860000007

  52. 40

    {10,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44}

    Returns: 943595488

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: