Statistics

Problem Statement for "MaximumLottery"

Problem Statement

A new lottery works as follows:

There is an urn containing some balls. On each ball there is one positive integer: a prize associated with the ball. (Different balls may have the same integer on them.) You are given these prizes in the int[] balls.

When playing the lottery, the player selects exactly K balls from the urn uniformly at random. The player wins the largest of the K amounts written on the selected balls. For example, drawing balls with $20, $47 and $33 written on them would give you $47.


The company running this lottery has an important question: what is the worth of a ticket that allows its owner to play the lottery once? If they sell them too cheap, they will (on average) lose money each time someone plays the lottery.

Calculate and return the smallest positive real number X such that if the company sells tickets for X, they aren't expected to lose money. (More precisely, the expected profit from selling someone a ticket and letting them play the lottery cannot be negative.)

Definition

Class:
MaximumLottery
Method:
ticketPrice
Parameters:
int[], int
Returns:
double
Method signature:
double ticketPrice(int[] balls, int K)
(be sure your method is public)

Notes

  • Your return value must have an absolute or a relative error at most 1e-9.
  • The phrase "the player selects exactly K balls from the urn uniformly at random" means that each set of K balls has the same probability of being selected. (One way in which this can be achieved is simply by drawing a random ball K times in a row, without replacement.)

Constraints

  • balls will have between 1 and 50 elements, inclusive.
  • Each element of balls will be between 1 and 10^6, inclusive.
  • K will be between 1 and the number of elements in balls, inclusive.

Examples

  1. {10, 10, 10, 10, 10, 10, 10}

    3

    Returns: 10.0

    Regardless of what three balls you select, the largest prize will always be $10. If you sell tickets cheaper, you will lose money. The smallest ticket price at which the company won't be losing money is clearly $10.

  2. {10, 50, 40, 20, 30}

    5

    Returns: 50.0

    The player will draw all five balls and win $50.

  3. {11, 12, 13, 14}

    3

    Returns: 13.75

    On average, one out of four games ends with the player winning $13 and the remaining three end with the player winning $14.

  4. {11, 12, 13, 14, 15, 16, 18}

    1

    Returns: 14.142857142857142

    With just a single ball drawn from the urn, whatever prize you draw you get.

  5. {1, 1, 2, 3, 5, 8, 13, 21}

    4

    Returns: 15.685714285714285

  6. {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, 1}

    10

    Returns: 1.0

  7. {5, 10, 7, 5, 9, 4, 10, 2, 4, 7, 8, 5, 10, 9, 3, 8, 1, 3, 9, 2, 2, 5, 9, 10, 9, 8, 7, 6, 1, 10, 5, 10, 9, 8, 6, 1, 10, 4, 4, 6, 7, 3, 3, 8, 4, 3, 2, 3, 10, 6}

    10

    Returns: 9.826756405974548

  8. {553021, 411420, 113336, 279829, 465485, 474, 684328, 128321, 434184, 70428, 387186, 21729, 277084, 43732, 147261, 189981, 775050, 536513, 876161, 514834, 210920, 821123, 810417, 851119, 518726, 553937, 475625, 590984, 594896, 10473, 728798, 77433, 183630, 876372, 157882, 966638, 569843, 354778, 666397, 909210, 48954, 920168, 652265, 245893, 746841, 64210, 397127}

    1

    Returns: 445000.3404255319

  9. {129131, 23294, 92893, 317434, 56510, 921961, 574469, 322611, 250734, 642412, 940029, 769672, 560871, 158550, 576642, 607921, 799464, 286430, 649056, 899995, 598564, 84624, 590306, 515118, 359364, 583556, 54718, 999541, 120162, 433563, 437934, 370927, 950648, 317522, 591734, 885305, 796630, 513022, 626693, 146436, 66623, 532546, 122754, 947174, 483672, 684671, 825080, 475809}

    48

    Returns: 999541.0

  10. {863676, 18747, 455694, 849005, 591324, 547488, 800498, 69407, 819584, 827563, 301601, 821817, 738991, 514015, 526799, 119673, 791625, 257027, 369297, 834931, 347194, 175026, 485031, 23692, 616273, 102956, 703528, 481790, 985345, 482900, 290233, 669025, 571391, 719341, 729054, 722653, 963344, 24940, 587411, 198481, 864135, 712613, 300999}

    2

    Returns: 694783.4407530454

  11. {42873, 809296, 276050, 568594, 506130, 402343, 71792, 757515, 824177, 114332, 921906, 546165, 743505, 618657, 628011, 500505, 563250, 780490, 829200, 379546, 606561, 326839, 432114, 807392, 715975, 939649, 941939, 214822, 767939, 663243, 95888, 984827, 107669, 537282, 848428, 319813, 424757, 999594, 348920, 565174, 876864, 377616, 892436, 114085, 855847, 978451, 97707, 896357, 652661}

    47

    Returns: 998985.8435374149

  12. {1647, 11462, 1851, 12841, 8779, 8335, 6902, 9494, 6856, 15238, 9815, 14590, 14433, 10403, 1795, 5089, 15719, 21, 902, 13853, 14989, 14349, 8446, 9633, 3359, 9932, 4059, 5563, 13864, 11032, 16304, 13960, 7685, 8622, 10257, 756, 12430, 15134, 5882, 12355, 1403, 5952, 5947, 2554, 15891, 13469, 1975, 7354, 15130, 5765}

    30

    Returns: 16081.225113745453

  13. {3, 2, 7, 1, 7, 8, 8, 6, 2, 7, 2, 2, 7, 7, 2, 3, 8, 8, 8, 2, 7, 6, 7, 4, 6, 7, 2, 3, 8, 6, 2, 5, 8, 2, 6, 1, 7, 2, 4, 4, 5, 5, 2, 1, 5, 3, 8, 4, 7}

    28

    Returns: 7.99954878060098

  14. {7, 4, 6, 2, 6, 2, 3, 2, 4, 3, 2, 3, 3, 3, 2, 2, 3, 7, 6, 2, 7, 5, 4, 6, 2, 6, 2, 1, 4, 3, 6, 2, 6, 7, 6, 7, 8, 7, 7, 8, 1, 4, 6, 1, 7, 2, 8, 2, 2}

    33

    Returns: 7.969604713303826

  15. {11, 6, 14, 16, 16, 4, 8, 7, 1, 16, 11, 5, 6, 10, 3, 2, 10, 2, 1, 9, 12, 7, 7, 12, 12, 5, 7, 15, 2, 10, 10, 14, 4, 14, 14, 12, 16, 9, 2, 16, 8, 9, 13, 2, 1, 13, 7}

    30

    Returns: 15.99480947879272

  16. {93025, 361918, 355471, 462643, 71072, 68635, 496149, 279767, 67483, 170144, 214672, 238479, 442603, 495601, 207045, 311127, 6228, 119734, 12440, 263304, 223346, 390773, 493891, 224667, 348572, 419918, 40198, 434866, 341260, 361471, 7846, 114597, 21556, 326078, 50949, 229297, 3524, 36610, 51651, 402073, 486579, 200246, 94134, 290724, 414639, 364762, 39647, 68438}

    26

    Returns: 493596.7276113966

  17. {427, 3619, 3797, 3333, 2725, 737, 2075, 3445, 3060, 805, 3092, 3093, 1446, 2423, 245, 250, 1568, 1033, 1826, 707, 63, 3465, 3504, 3411, 3466, 1046, 1262, 3078, 3769, 2152, 1209, 616, 325, 1979, 1051, 578, 144, 1123, 1005, 1043, 2394, 3427, 3999, 193, 1372, 1195, 1895}

    41

    Returns: 3972.6294030317654

  18. {3968, 4015, 3774, 2534, 3357, 3685, 1504, 105, 3506, 3993, 4012, 3343, 2814, 3072, 2474, 2518, 3232, 3085, 292, 2202, 1161, 3829, 3215, 831, 882, 279, 3013, 2787, 1209, 9, 2134, 2878, 1311, 326, 3378, 3940, 2650, 1209, 2177, 2099, 2710, 3349, 914, 1684, 1447}

    12

    Returns: 3928.4548346644165

  19. {2013, 3774, 2793, 1279, 2957, 914, 1200, 1456, 1864, 2625, 1688, 2042, 335, 2995, 3117, 1409, 4016, 1395, 1584, 3299, 440, 3842, 2678, 612, 2121, 781, 1135, 1707, 2243, 3191, 910, 2094, 2931, 980, 3079, 3050, 1844, 2384, 2056, 2629, 314, 1700, 2427, 3655, 2665, 936, 1199, 1500, 2134}

    17

    Returns: 3761.1640623719677

  20. {38, 27, 5, 35, 28, 26, 64, 64, 10, 49, 3, 20, 14, 54, 39, 29, 53, 25, 12, 28, 29, 12, 54, 40, 41, 48, 16, 12, 41, 59, 28, 16, 12, 44, 62, 29, 8, 41, 40, 49, 34, 8, 10, 33, 59, 29, 63}

    20

    Returns: 63.03855705175557

  21. {32611, 43071, 27490, 23262, 24826, 31363, 5441, 3852, 34150, 38627, 26026, 44998, 44135, 22783, 42963, 48851, 24223, 20604, 64676, 9901, 4613, 51234, 60846, 58990, 38571, 12314, 64530, 35453, 43750, 36999, 28442, 56032, 9893, 33480, 50143, 42410, 60255, 38265, 21113, 31727, 23906, 47536, 30177, 40500, 4754, 28390, 62085}

    23

    Returns: 63684.08335447851

  22. {5, 5, 7, 4, 8, 8, 1, 2, 3, 7, 8, 3, 4, 1, 7, 8, 2, 1, 8, 8, 3, 3, 4, 5, 6, 4, 8, 5, 8, 5, 6, 2, 4, 5, 4, 1, 3, 4, 8, 2, 6, 4, 6, 2, 5}

    25

    Returns: 7.999806076261166

  23. {1479, 572, 675, 323, 755, 229, 736, 421, 1172, 172, 1314, 760, 355, 1842, 1130, 405, 1223, 801, 2028, 590, 559, 997, 985, 1280, 1053, 1862, 108, 1266, 773, 105, 1765, 714, 1101, 1995, 773, 1838, 53, 1514, 1014, 1645, 734, 723, 734, 206, 882, 1291, 1650, 1229, 1097}

    13

    Returns: 1876.0194575546614

  24. {1885, 357, 3861, 2508, 1933, 2424, 3740, 1468, 1449, 2481, 3770, 2369, 2388, 425, 2513, 311, 562, 3275, 3482, 1200, 3101, 3151, 1837, 3388, 3646, 1495, 2069, 3282, 2625, 2746, 1022, 3098, 3567, 1152, 736, 3553, 2045, 1931, 29, 2106, 208, 2762, 3250, 2482, 1623, 2078, 555, 415, 1990, 1431}

    8

    Returns: 3542.5317842495692

  25. {2740, 16358, 8550, 9195, 12059, 6697, 1572, 8535, 15967, 7628, 3584, 10016, 6049, 13002, 9214, 6607, 9184, 5258, 5291, 10490, 5022, 9117, 15797, 3235, 9362, 8566, 4949, 12814, 7188, 7269, 5837, 2826, 9505, 4776, 15242, 9674, 1035, 3493, 7238, 6794, 3484, 6454, 16365, 12559, 9911, 8368, 399, 10991, 11809}

    25

    Returns: 16169.301680185506

  26. {22, 17, 15, 9, 16, 32, 13, 3, 11, 2, 21, 15, 24, 15, 16, 32, 24, 13, 28, 12, 30, 15, 3, 27, 30, 15, 28, 2, 28, 5, 32, 13, 26, 13, 1, 16, 32, 1, 19, 31, 21, 20, 25, 15, 4, 14, 14, 32}

    9

    Returns: 30.80459507750801

  27. {209679, 210840, 73375, 219468, 187289, 6777, 178080, 56123, 189719, 202279, 137351, 80167, 27681, 112784, 27682, 137222, 135555, 92408, 196228, 195879, 121100, 69887, 123646, 55626, 70443, 188459, 26937, 76086, 91544, 204541, 141858, 32957, 80725, 126290, 168921, 238278, 137713, 49389, 183845, 134512, 4959, 146338, 140310, 243759, 244834, 78936, 190575, 70750, 109011}

    31

    Returns: 242754.80732629323

  28. {13, 16, 7, 6, 12, 2, 6, 8, 16, 16, 14, 2, 16, 8, 11, 8, 13, 15, 5, 6, 6, 7, 11, 1, 7, 15, 6, 10, 14, 16, 14, 1, 6, 14, 13, 2, 2, 2, 4, 7, 16, 7, 2, 4, 1}

    9

    Returns: 15.536191472239476

  29. {145881, 51674, 61344, 188116, 253389, 4745, 145991, 241235, 233837, 97326, 64630, 135645, 193288, 244238, 28262, 257951, 17182, 223274, 42945, 110124, 194356, 102850, 120831, 75082, 107970, 259768, 55924, 152360, 52135, 256906, 101800, 19815, 78754, 135522, 77678, 147062, 195569, 77000, 174434, 194148, 66628, 75173, 224526, 213245, 166521, 94272, 196659}

    19

    Returns: 255823.73500014274

  30. {21863, 8522, 13212, 17020, 13535, 10020, 28569, 3757, 23713, 50688, 12650, 8397, 63115, 2288, 16083, 22655, 43747, 17158, 17248, 36534, 29379, 18177, 6742, 50836, 20810, 54938, 3827, 9519, 31994, 55923, 8298, 46420, 31824, 46753, 34916, 24683, 5797, 40054, 5839, 23234, 7754, 40800, 40339, 57271, 44597}

    9

    Returns: 53556.716109650624

  31. {750, 670, 781, 99, 1908, 943, 1064, 1711, 1967, 22, 214, 1398, 1668, 381, 311, 1401, 855, 1064, 1401, 495, 623, 1846, 1551, 1377, 829, 1056, 1124, 1875, 1024, 1976, 727, 1677, 1592, 813, 145, 1326, 183, 964, 277, 478, 1122, 981, 1975, 1808, 573}

    26

    Returns: 1968.7826017553857

  32. {6, 5, 1, 5, 6, 6, 6, 3, 2, 5, 2, 8, 8, 6, 7, 3, 5, 2, 8, 7, 5, 4, 4, 1, 3, 1, 5, 7, 8, 4, 4, 1, 5, 4, 1, 6, 5, 3, 7, 2, 2, 4, 3, 3, 2, 7, 6, 5, 1}

    9

    Returns: 7.41613464941828

  33. {725, 36, 1259, 1219, 1679, 1535, 1355, 1001, 1154, 877, 1380, 1653, 1524, 867, 561, 1454, 119, 1902, 607, 1442, 1621, 367, 353, 302, 1719, 632, 759, 690, 1856, 284, 875, 1501, 1569, 789, 2039, 289, 2034, 814, 231, 83, 1324, 798, 1559, 52, 568, 1610, 1507, 950, 446, 1024}

    35

    Returns: 2024.238689280132

  34. {1889, 1624, 1725, 1982, 142, 680, 636, 794, 1456, 1438, 605, 194, 150, 522, 754, 736, 207, 49, 1464, 864, 96, 546, 125, 1407, 1037, 1237, 1698, 587, 1834, 1818, 661, 655, 1747, 54, 527, 744, 2016, 519, 1709, 1517, 103, 36, 1880, 835, 1240, 688}

    27

    Returns: 1984.5541892022666

  35. {3403, 1507, 2632, 829, 3016, 1826, 1726, 3748, 3637, 1534, 1849, 2253, 197, 785, 3237, 393, 2985, 503, 3588, 320, 871, 2096, 2797, 1729, 3011, 83, 2838, 1817, 1731, 1605, 1519, 2766, 1923, 3180, 491, 951, 1059, 3434, 2674, 2979, 3676, 3982, 3782, 4064, 1386, 298, 3417}

    36

    Returns: 4034.1388890902026

  36. {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, 45, 46, 47, 48, 49, 50 }

    25

    Returns: 49.03846153846154

  37. {111111, 222222, 333333, 555555, 888888, 131313, 212121, 1000000, 999999, 111111, 222222, 333333, 555555, 888888, 131313, 212121, 1000000, 999999, 111111, 222222, 333333, 555555, 888888, 131313, 212121, 1000000, 999999, 111111, 222222, 333333, 555555, 888888, 131313, 212121, 1000000, 999999, 111111, 222222, 333333, 555555, 888888, 131313, 212121, 1000000, 999999 }

    25

    Returns: 999993.5374597621

  38. {13, 15, 17, 23, 2452, 2345, 64, 4363, 37, 35635, 3453, 36346, 376, 3634, 3456, 353, 3, 21, 1, 54, 13, 43 }

    7

    Returns: 21285.32775705976

  39. {10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10009, 10010, 10011, 10012, 10013, 10014, 10015, 10016, 10017, 10018, 10019, 10020, 10021, 10022, 10023, 10024, 10025, 10026, 10027, 10028, 10029, 10030, 10031, 10032, 10033, 10034, 10035, 10036, 10037, 10038, 10039, 10040, 10041, 10042, 10043, 10044, 10045, 10046, 10047, 10048, 10049 }

    10

    Returns: 10045.363636363636

  40. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    2

    Returns: 1000000.0

  41. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    25

    Returns: 1000000.0000000001

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: