Statistics

Problem Statement for "AverageVarianceSubset"

Problem Statement

In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its mean. As a special case, we can compute the variance of a nonempty finite set X = { x_1, ..., x_n } as follows:
  1. Let mu = (x_1 + ... + x_n) / n be the mean of the set.
  2. Let y_i = (x_i - mu)^2 be the square of the difference between x_i and the mean.
  3. The variance of X, denoted var(X), can now be computed as the average of all y_i. (In other words, as the sum of all y_i, divided by n.)
For example, if X = { 0, 1 }, we have mu = 1/2, then y_1 = y_2 = 1/4, and finally var(X) = (1/4 + 1/4) / 2 = 1/4.

The range of a nonempty finite set is the difference between its maximum and its minimum. For example, the range of the set { 40, 51, 67, 70 } is 70 - 40 = 30.

You are given a int[] s that contains a set of distinct positive integers. You are also given an int R.

Consider all nonempty subsets of s with range less than or equal to R. Alice computed the variance of each of those subsets. Bob took all Alice's results and computed their average. Compute and return the number computed by Bob.

Definition

Class:
AverageVarianceSubset
Method:
average
Parameters:
int[], int
Returns:
double
Method signature:
double average(int[] s, int R)
(be sure your method is public)

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • s will contain between 1 and 50 elements, inclusive.
  • Elements in s will be distinct.
  • Each element in s will be between 1 and 1,000,000,000, inclusive.
  • R will be between 0 and 1,000,000,000, inclusive.

Examples

  1. {1,2,3}

    1

    Returns: 0.1

    This set has seven nonempty subsets. Out of those, five have range at most 1: {1}, {2}, {3}, {1,2}, and {2,3}. Alice computed the variance of each of these subsets: The variance of {1} is 0. The variance of {2} is 0. The variance of {3} is 0. The variance of {1,2} is 1/4. The variance of {2,3} is 1/4. Bob took Alice's results and computed their average: (0 + 0 + 0 + 1/4 + 1/4) / 5 = 1/10.

  2. {1,2,3}

    3

    Returns: 0.3095238095238096

    This time Alice will consider all seven nonempty subsets. The two new subsets: The variance of {1,3} is 1. The variance of {1,2,3} is 2/3. Bob will then compute the value (0+0+0+1/4+1/4+1+2/3)/7 = 13/42.

  3. {5,1,3,2}

    1000000000

    Returns: 1.2476851851851847

  4. {1,11,111,1111,11111,111111,1111111,11111111,111111111}

    123456

    Returns: 1.1349430459217174E9

  5. {1,11,111,1111,11111,111111,1111111,11111111,111111111}

    999999999

    Returns: 9.989198236452121E14

  6. {1,1000000000}

    1000000000

    Returns: 8.3333333166666672E16

    Note that the answer can be very large.

  7. {1,1000000000}

    1

    Returns: 0.0

  8. {546392386, 989939501, 138350642, 296751024, 511315675, 737741611, 364070805, 516045285, 340946329, 639018763, 5567688, 24109720, 808000925, 169150440, 913254493, 225242497, 4005195, 592394468, 513392111, 129856382, 568317331, 569671607, 697749142, 185671536, 652828828, 735149658, 960256764, 730150690, 162219083, 606024985, 204415228, 555126857, 608193692, 514250468, 223534483, 980890475, 425608006, 221908606, 2414882, 521893730, 899538350, 849151763, 991445587, 995744182, 575829776, 823233054, 961951786, 659945588, 565883473, 153396145}

    5000000000

    Returns: 4.225484491729432E16

  9. {546392386, 989939501, 138350642, 296751024, 511315675, 737741611, 364070805, 516045285, 340946329, 639018763, 5567688, 24109720, 808000925, 169150440, 913254493, 225242497, 4005195, 592394468, 513392111, 129856382, 568317331, 569671607, 697749142, 185671536, 652828828, 735149658, 960256764, 730150690, 162219083, 606024985, 204415228, 555126857, 608193692, 514250468, 223534483, 980890475, 425608006, 221908606, 2414882, 521893730, 899538350, 849151763, 991445587, 995744182, 575829776, 823233054, 961951786, 659945588, 565883473, 153396145}

    999999999

    Returns: 8.6605741190155488E16

  10. {100111, 40673424, 82725730, 61426970, 90545993, 14853738, 15960590, 61839389, 89232777, 90827479, 5210525, 18358699, 76885215, 10330620, 64018276, 67936379}

    4661769

    Returns: 7.226047157526333E11

  11. {92079421, 24490203, 68521821, 56302955, 48050912, 20045721}

    81185186

    Returns: 4.418545814671306E14

  12. {640277913, 979237163, 946073422, 901920103, 273366783, 283366182, 7361318, 40088963, 939868912, 149419996}

    885875194

    Returns: 8.1217633156999472E16

  13. {8377772, 4325682, 3815532, 58160, 1154755, 2202228, 2335266, 2756578, 2623976}

    2071060

    Returns: 3.3483413893750946E11

  14. {62716, 29157, 17861}

    30623

    Returns: 7974976.0

  15. {19843}

    2524

    Returns: 0.0

  16. {3942, 2514, 2459, 25, 1531, 4879, 8926, 5713, 9818, 6328, 6528, 2890, 2574, 389, 5558, 2156, 1732, 769, 1618, 885, 4650, 5329, 3541, 1179, 9313, 9835, 8836, 2743, 6145, 8696, 7170, 3472, 3009, 5683}

    5771

    Returns: 3069218.064997477

  17. {7202917, 6487150, 2747944, 3743508, 1756836, 2829438, 888840, 5718227, 3124436, 8844351, 8569365, 3679813, 3571951, 8657358, 3255987, 7187020}

    8430482

    Returns: 5.893692047168006E12

  18. {83, 14, 89, 26, 72, 15, 69, 77, 98, 52, 44, 20}

    56

    Returns: 271.55099013742023

  19. {702543494, 683921340, 564873158, 913712752, 739280760, 940565212, 992713060, 839840239, 170297678, 983209364, 671024892, 876568960, 126454038, 750960305, 207452667, 527700410, 634715654, 500748391}

    70578606

    Returns: 4.180050359422426E14

  20. {2570056, 4183414, 3262530, 8375110, 1255240, 8476913, 6825934, 8253025, 6440635, 9597537, 151038, 1509205, 6669108, 2174991, 4816413, 5947919, 6636367, 1370918, 7826793, 6838152, 6042022, 8496126, 5235920, 4143414}

    1076204

    Returns: 8.159245350412267E10

  21. {34, 85, 26, 55, 51, 88, 100, 2, 59, 43, 67, 98, 99, 87, 66, 53, 50, 39, 92, 54, 14, 49, 80, 13, 48, 52, 45, 30, 90, 94, 81, 95, 61, 3, 96, 84, 56, 93, 23, 75, 97, 18, 6, 76, 77, 7, 63, 73, 78, 41}

    69

    Returns: 396.30938647492945

  22. {681426634, 313687703, 37048703}

    690828158

    Returns: 3.2344411442461212E16

  23. {411907606, 712631494, 236250292, 287342635, 995451424, 226060243, 802442732, 598441540, 88488814, 506063055, 490274535, 473335347, 690501372, 595585164, 502250613, 759756615, 309090207, 957723068, 691194792, 421808942, 61603254, 67894957, 87532683, 683892658, 94660840, 859543328, 982413993, 929053854, 175126817, 881763152, 663658100, 79047314, 884963024, 311455431, 835838412, 540007721, 238291543, 534981370}

    562677087

    Returns: 2.8806869904067312E16

  24. {89, 37, 30, 93, 55, 46, 98, 32, 56, 57, 62, 84, 87, 94, 42, 9, 39, 28, 24, 26, 43, 74, 19, 59, 81}

    20

    Returns: 42.77562902451421

  25. {7824, 5291, 8724, 1894, 6417, 5024, 2201, 9769, 2035, 1976, 4060, 4813, 7009, 9264, 336, 9996, 2344, 1650, 9395, 7339, 8804}

    5304

    Returns: 2843753.0848286124

  26. {16793076, 94876239, 96366692}

    23530022

    Returns: 1.388406340755E11

  27. {9226, 88855, 13649, 63238, 87447, 70212, 41500, 44318, 72599, 83558, 24215, 69355, 47228, 31729, 34100, 29312, 13098, 28463, 942, 81973, 61027}

    196

    Returns: 0.0

  28. {296, 225, 114, 126, 939, 353, 212, 311, 829, 559}

    838

    Returns: 63684.1590693589

  29. {6317631, 3819618, 24379, 3118405, 4423652, 7348642, 9840485, 6815051, 6534861, 1669832, 7578601, 3616904, 7502970, 6019315, 5292981, 6921070, 9090449, 2053335, 3731867, 8540647, 6897758, 428413, 182263, 5695729, 9627024, 202155, 1751438, 907554, 3907441, 594658, 8423821, 9088346, 4104260, 1173810, 9180271, 1946538, 9564871, 6174822, 4712604, 2607029, 3503535, 7828085, 608401, 9853899}

    6438867

    Returns: 4.041148877787322E12

  30. {72767582, 94813448, 22736967, 66379638, 3729687, 9637793, 33664066, 44630052, 86913266, 41366797, 68180337, 24116255, 23883254, 86713065, 57899637, 99208285, 64576412}

    79556327

    Returns: 5.93607371168726E14

  31. {274, 990, 819, 902, 607, 646, 541, 680, 114, 158, 265, 257, 618, 321, 386, 268, 447, 785, 275, 917, 673, 529, 827, 675, 833, 551, 457, 564}

    323

    Returns: 10439.125389128623

  32. {834, 6929, 4074, 9919, 2208, 2336, 1426, 8775, 1055, 3430, 5979, 8863}

    6605

    Returns: 3998423.572756056

  33. {96080, 14597, 23462, 4824, 38314, 11111, 68156, 64482, 39128, 92745, 23671, 97821, 5818, 92413, 64584, 9035, 50010, 36295, 15222, 38013, 61033, 66000, 92512, 77434, 79515, 45178, 13781, 83630, 16076, 49545, 17133, 84880, 42112, 99094, 17397, 87775, 85330, 75951, 21391, 53376, 91343, 11444, 84137, 38448, 57359, 80982, 56940, 80906, 95282}

    13914

    Returns: 1.7926701506868303E7

  34. {1029209, 5597070, 2843500, 2870741, 7498396, 82373, 73889, 7148952, 6071005, 8140615, 1345056, 8238882, 98524, 9036454, 470105, 2398039, 7502209, 9267338, 8310452, 120757, 4427206, 8965494, 9887376, 8580981, 5378536, 4394918, 9029326, 4373230, 2798412, 5726172, 3142351, 1599283, 6097503, 5152041, 7249177, 6025566, 7244807, 4994161, 2068735, 1162434, 6098003, 2228683, 8240996, 8572858}

    3453396

    Returns: 1.2279596725765544E12

  35. {85599282, 7556036, 34109197, 86404385, 29448700, 4771065, 56187221, 53535653, 65985571, 6861157, 48250445, 96170335, 14797249, 14660185, 42551273, 62284165, 99944163, 77792403}

    96964233

    Returns: 9.004043007320485E14

  36. {6275745, 5651261, 5315860, 7204717, 5544377, 9077174, 8883544}

    1924814

    Returns: 3.1680594658791797E11

  37. {8204086, 82911837, 34909138, 41636784, 1242581, 90639334, 46938175, 32382569, 59384573, 97104179, 76965746, 35874893}

    25426664

    Returns: 4.275021415869642E13

  38. {77501807, 40852405, 16934663, 1955793, 40174930, 23704168, 2875300, 24798284, 44236785, 5166707, 3639086, 36441065, 28864991, 24408186, 78459595, 33052863, 74524347, 37095378, 57081389, 2121969, 95651435, 95882697, 76795947, 82504555, 42325225, 51036096, 16459500, 69762670, 87106266, 99077429, 19266294, 77760001, 59049639, 352481, 27116306, 73966667, 64721547, 20001419, 52657231, 20226466, 4183037, 46067316, 48984712, 71783812, 86817011, 89290278}

    88120510

    Returns: 7.219732457130886E14

  39. {9152, 8658, 2947, 1812, 7678, 9194, 7589, 9898, 3284, 7528, 3567, 7493, 9762}

    2738

    Returns: 720453.4936344291

  40. {889461, 432098, 276690, 732661, 918242, 686220, 999136, 473794, 16490, 904984, 669268, 492487, 201126, 534035, 272098, 900770, 675873, 705433, 552697, 727466, 899213, 383177, 582793, 122957, 597521, 67745, 993669, 507270, 470710, 99864, 383125, 290184, 937885, 291113, 939113}

    316591

    Returns: 9.877446774654976E9

  41. {89340519, 46029511, 43155257, 76661228, 89219653, 53431044, 71037700, 94439809, 99506827, 33905278, 84651458, 1473727, 26702896, 36315824, 6974219, 60193435, 73788833, 938111, 16479657, 10929865, 36277068, 22425937}

    95413447

    Returns: 8.589746912837722E14

  42. {4608189, 4815468, 4449889, 7535417, 2027768, 8816614, 3436157, 810280, 1788240, 94490, 6440427, 2476664, 5427548, 7350720, 5444701, 7022179, 6591060, 2716355, 5714451, 1204570, 8164903, 3919173, 1953806, 7039265, 3607667, 5020639, 4192507, 3133804, 737849, 5153403, 4251118, 1282033, 6026364, 661456, 9776375, 7572862, 4479257, 9273706, 494583}

    2372738

    Returns: 4.94174744759919E11

  43. {459, 922, 227, 769, 635, 173, 37, 269, 439, 850, 430, 571, 741, 830, 308, 431, 311, 195, 421, 645, 306, 405, 731, 277, 752, 128, 935, 434, 282, 212, 288, 955, 316, 323, 31, 496, 404, 628, 646, 700, 372, 911, 384, 713, 517, 749, 45, 982, 127, 357}

    767

    Returns: 46568.56538338094

  44. {860, 696, 713, 290, 159, 622}

    357

    Returns: 5030.656067251454

  45. {274654094, 44834117, 125541966, 822654297, 573440468, 474439444, 241512647, 642633130, 358441527, 857293406, 675041486, 50831087, 47382244, 840433440, 10286823, 436832381, 319992800, 124845186, 292293988, 459451674, 658574089, 351525942, 704052073, 87566287, 996682829, 910141960, 325147462, 288029222, 398048120}

    436267037

    Returns: 1.9309089414847832E16

  46. {75470, 83413, 42492, 79712, 14089, 98220, 84888, 8147, 30667, 97952, 5424, 66688, 31107, 68473, 75493}

    80743

    Returns: 6.790705566234058E8

  47. {479923720, 130451956, 980461795, 333381347, 304345567, 416120051, 846601006, 388205426, 938956116, 786046130, 10372881, 181395401, 653198307, 805142352, 140236753, 966341210, 775326157, 61576555, 907285425, 775160396, 39196548, 918870178, 33035814, 717767284, 464136230, 186493170, 116001579, 319040713, 621297288, 926373283, 726738191, 167850008}

    997486791

    Returns: 1.04190788088841808E17

  48. {570926, 446873, 812034, 247080, 788362, 220079, 732735, 935438, 739221, 20971, 501952, 152850, 380043, 812377, 999966, 802189, 648250, 931220, 875496, 950247}

    326736

    Returns: 8.16956084716152E9

  49. {86, 54}

    49

    Returns: 85.33333333333333

  50. {4351, 3742, 6621, 2402, 5502, 3444, 3443, 290, 7971, 1105, 5473, 3627, 7105, 2375, 9756, 5573, 7414, 7364, 3435, 7238, 3889, 3762, 827, 190, 3943, 2568, 573, 7322, 9186, 9127, 8219, 3379, 5744, 5733, 7132, 2847, 5997, 4500, 2550, 6043, 2195, 4467, 1789, 4101, 8008}

    2675

    Returns: 720586.1404302593

  51. {9513, 314487, 240424, 79164, 180658, 26918, 534634, 456826, 843658, 956673, 125825, 933613, 193975, 673697, 284117, 384564, 384432, 60699, 570829, 292619, 438403, 262455, 101509, 62461, 787777, 888645, 197256, 135627, 830998, 531908}

    659634

    Returns: 3.0688378333494183E10

  52. {2956, 131, 7935, 9620, 7094, 8424, 6215, 3135, 556, 1150, 9089, 373, 5851, 4749, 6924, 1847, 987, 7934, 3581, 5605}

    4534

    Returns: 1763779.8400997238

  53. {9700, 6701, 4509, 6274, 5247, 1535, 5234, 1050, 2304, 4065, 1679}

    738

    Returns: 37016.8308080809

  54. {706, 887, 782, 785, 580, 7, 180, 515, 693, 80, 466, 101, 498, 471, 596, 925, 224, 329, 182, 455, 919, 99, 76, 444, 290, 589, 119, 897, 623, 996, 637, 490, 208, 912, 9, 882, 68, 617, 910}

    369

    Returns: 13108.493261901698

  55. {90497204, 21708707, 67599204, 75162403, 71631132, 47722446, 16082350, 34946625, 8989684, 91475855, 66933729, 38906180, 83231120, 40825733, 52849381, 23101106, 10823534, 91674829, 94150003, 28303753, 53965046, 64427835, 96998342, 80054590, 78190466, 49898093, 65154390, 70636447, 4903209, 59933013, 22194172, 97932129, 21207001, 39874836, 24172526}

    89745214

    Returns: 7.228027549852426E14

  56. {61, 32, 56, 23, 22, 88, 20, 92, 65, 96, 45, 42, 43, 6, 17, 57, 58, 39, 68, 87, 19, 25, 59, 26, 29, 37, 48, 81, 84, 83, 16, 82, 93, 12, 79, 34, 99, 8, 28, 71}

    43

    Returns: 175.7754009567215

  57. {41800, 897372, 945486, 795388, 990266, 653554, 977459, 793523, 992708, 812705, 834610, 760364, 228103, 833718, 645204, 623047, 196747, 234772, 342463, 539146, 932691, 495000, 246001, 736229, 445328, 664845}

    693698

    Returns: 3.578646771077958E10

  58. {87561939, 19055996, 51273433, 90175077, 48599297, 86076517, 52787583, 89033692, 84197280, 94288796, 53092868, 43751145, 85927265, 48956301, 75366690, 36185123, 62068270, 78986262, 58953804, 29889482, 61538163, 14508561, 76650677, 95814943, 86143144, 23489499, 49069169, 30620456, 76379704, 9177870, 63041488, 27212291, 93107364, 7593118, 41013378, 92072452, 27910286, 3007541}

    47949860

    Returns: 2.559305019142135E14

  59. {839}

    619

    Returns: 0.0

  60. {1}

    0

    Returns: 0.0

  61. {1,2,3}

    0

    Returns: 0.0

  62. {1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111 }

    999999999

    Returns: 9.989198236452121E14

  63. {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

    Returns: 195.6518041932746

  64. {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 }

    100

    Returns: 203.81879605977974

  65. {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 }

    1000000000

    Returns: 110.64633882718594

  66. {1, 2, 3 }

    1

    Returns: 0.1

  67. {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 }

    100

    Returns: 82.30931119573724

  68. {1, 2, 3 }

    3

    Returns: 0.3095238095238096

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: