Statistics

Problem Statement for "AverageVarianceSubtree"

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 collection of numbers X = { x_1, ..., x_n } as follows:
  1. Let mu = (x_1 + ... + x_n) / n be the mean of the collection.
  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.

Another example: suppose X = { 0, 0, 0, 1 }. Now we have mu = 1/4. Then we compute that y_1 = y_2 = y_3 = 1/16 and y_4 = 9/16. The average of these four values is 3/16.

You are given a tree T with n vertices, labeled 0 through n-1. More precisely, you are given the int[] p with n-1 elements that describes the edges of the tree. For each valid i, there is an edge between (i+1) and p[i]. The constraints ensure that this will always be a valid tree.

Each vertex of the tree has a positive integer weight. You are given these weights in the int[] weight with n elements.

A subtree of the tree T is any subgraph that is a tree. Alice found all nonempty subtrees of T. For each of them, she took the collection of weights of its vertices and she computed its variance. Bob then computed the average of all the variances computed by Alice. Compute and return the number Bob computed.

Definition

Class:
AverageVarianceSubtree
Method:
average
Parameters:
int[], int[]
Returns:
double
Method signature:
double average(int[] p, int[] weight)
(be sure your method is public)

Notes

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

Constraints

  • weight will contain between 1 and 50 elements, inclusive.
  • Each element in weight will be between 1 and 1,000,000,000, inclusive.
  • p will contain exactly |weight|-1 elements.
  • For each i, 0 <= p[i] <= i.

Examples

  1. {0,1}

    {10,20,30}

    Returns: 19.444444444444443

    The tree contains the edges 1-0 and 2-1. Thus, it looks as follows: 0-1-2. This tree has six different subtrees. These correspond to the following collections of weights: {10}, {20}, {30}, {10,20}, {20,30}, and {10,20,30}. Their variances are 0, 0, 0, 25, 25, and 200/3. The return value is the average of these six numbers.

  2. {0,1,1}

    {10,20,7,6}

    Returns: 23.0145202020202

    This time the tree looks as shown below. (The numbers in the figure are the weights of those vertices.) 10 - 20 - 7 | 6 This tree has 11 nonempty subtrees. Below we list the collection of weights and its variance for each of the subtrees. {10}, 0.0000000000000000 {20}, 0.0000000000000000 {7}, 0.0000000000000000 {6}, 0.0000000000000000 {10,20}, 25.0000000000000000 {7,20}, 42.2500000000000000 {6,20}, 49.0000000000000000 {20,7,6}, 40.6666666666666643 {10,20,6}, 34.6666666666666643 {10,20,7}, 30.8888888888888857 {10,20,7,6}, 30.6875000000000000

  3. {0}

    {1,1000000000}

    Returns: 8.3333333166666672E16

    The answer can be very large

  4. {0,0,1,0,2,3,3,6}

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

    Returns: 4.432586365551198E14

  5. {}

    {712}

    Returns: 0.0

  6. {0, 0, 2, 2, 1, 2, 0, 3, 8, 1, 10, 2, 7, 11, 12, 2, 0, 15, 2, 8, 8, 20, 1, 17, 3, 6, 8, 5, 13, 9, 23, 7, 20, 30, 16, 30, 12, 11, 15, 6, 20, 3, 12, 23, 12, 22, 7, 22, 34}

    {660363919, 845152057, 765999598, 226021296, 916094168, 549161879, 429081243, 99575640, 432956892, 573039637, 648642658, 980206343, 877736396, 511335780, 493014697, 425539383, 185832028, 964814251, 263094572, 591315636, 842520615, 534328502, 25918827, 97698063, 43311026, 455722822, 563764012, 800261312, 83168632, 842214653, 489214095, 746434271, 48677601, 724334488, 839011728, 871627873, 22418215, 160152039, 59030082, 284004456, 210500927, 105086820, 865647753, 661572302, 796735443, 2008755, 123548179, 801582152, 344226653, 138712590}

    Returns: 8.9782939790271888E16

  7. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {660363919, 845152057, 765999598, 226021296, 916094168, 549161879, 429081243, 99575640, 432956892, 573039637, 648642658, 980206343, 877736396, 511335780, 493014697, 425539383, 185832028, 964814251, 263094572, 591315636, 842520615, 534328502, 25918827, 97698063, 43311026, 455722822, 563764012, 800261312, 83168632, 842214653, 489214095, 746434271, 48677601, 724334488, 839011728, 871627873, 22418215, 160152039, 59030082, 284004456, 210500927, 105086820, 865647753, 661572302, 796735443, 2008755, 123548179, 801582152, 344226653, 138712590}

    Returns: 9.2341546630877136E16

  8. {0, 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}

    {660363919, 845152057, 765999598, 226021296, 916094168, 549161879, 429081243, 99575640, 432956892, 573039637, 648642658, 980206343, 877736396, 511335780, 493014697, 425539383, 185832028, 964814251, 263094572, 591315636, 842520615, 534328502, 25918827, 97698063, 43311026, 455722822, 563764012, 800261312, 83168632, 842214653, 489214095, 746434271, 48677601, 724334488, 839011728, 871627873, 22418215, 160152039, 59030082, 284004456, 210500927, 105086820, 865647753, 661572302, 796735443, 2008755, 123548179, 801582152, 344226653, 138712590}

    Returns: 8.46043715600624E16

  9. {0, 0, 2, 1, 3, 0, 2, 0, 8, 1, 7, 8, 11, 11, 2, 0, 13, 17}

    {20146994, 56842526, 62116007, 10796324, 3031361, 56689833, 44795451, 97458535, 66040022, 60072579, 23126536, 15908970, 45584247, 22955952, 86294218, 53632840, 93561578, 26799736, 28602718}

    Returns: 7.57873154375453E14

  10. {0, 1}

    {16167747, 79460830, 87382100}

    Returns: 3.387954984054893E14

  11. {0, 0, 0, 0, 4, 3, 4, 1, 7, 2, 9, 3}

    {6805, 8741, 5844, 5397, 9843, 2353, 1027, 2425, 6396, 4008, 6681, 4458, 2894}

    Returns: 5979755.959004949

  12. {0, 1, 0, 3, 0, 5, 2, 1, 5}

    {381, 623, 961, 758, 525, 745, 14, 241, 519, 434}

    Returns: 48947.572617558

  13. {0, 1, 0, 2, 1, 0, 0, 2, 7, 4, 9, 7, 0, 13, 0, 3, 2, 0, 2, 18, 8, 21, 0, 14, 13, 17, 15, 18, 11, 14, 28, 16, 27, 27, 13, 15, 31, 36, 12, 37, 21, 34, 3, 36, 5, 24, 2}

    {140941, 500677, 837176, 821904, 710530, 333889, 465119, 598269, 689332, 362590, 338457, 171310, 451860, 957184, 461137, 780393, 999899, 127536, 475885, 839730, 474054, 356292, 373664, 423267, 149580, 823800, 589435, 727863, 619980, 363909, 102712, 880956, 628436, 174316, 389275, 23786, 228391, 188003, 570407, 940197, 510968, 343896, 86194, 287409, 510158, 586634, 808484, 366653}

    Returns: 6.644167948000516E10

  14. {0, 0, 1, 2, 0, 2, 4, 6, 7, 9, 4, 4, 10, 10, 10, 9, 16, 15, 2, 12, 7, 11, 10, 17, 12, 6, 13, 14, 0, 3, 26, 0, 11}

    {2015007, 2759825, 5978366, 6733037, 5720353, 3884324, 9163102, 2087789, 5948501, 2241090, 8365330, 3691845, 6904835, 2896339, 8996667, 8703514, 6677776, 7292244, 5383562, 6245000, 4839280, 1000968, 7884481, 546158, 6501773, 9816630, 9374540, 6706488, 3761228, 1624326, 5544096, 4129233, 4538493, 962367}

    Returns: 7.079188651285336E12

  15. {0, 0, 1, 1, 4}

    {81525, 11849, 84684, 8333, 32081, 56261}

    Returns: 5.1402745849855554E8

  16. {0, 0, 0, 0, 1, 0, 6, 6, 8, 0, 8, 5, 4, 1, 3, 7, 6, 6, 15, 18, 16, 18, 13, 20, 9, 14, 24, 12, 1, 16, 10, 2, 17, 32, 5, 19, 19, 1, 0, 4, 37, 6, 23, 3, 26, 31, 33, 21}

    {8907889, 1722345, 3095145, 8983742, 9104981, 4387311, 9052580, 8681797, 6712665, 9747104, 9276238, 1406941, 1415545, 5077963, 5780888, 886192, 9711857, 7283941, 5760679, 8616663, 9066229, 6568365, 6103160, 8903149, 6946787, 7340748, 2009730, 4746230, 9556859, 9159770, 7233024, 7553482, 9061564, 601691, 223063, 6499383, 6955445, 4245792, 5260148, 9730451, 2528947, 6880932, 7423485, 794956, 8888432, 5257963, 1205357, 8252126, 4240199}

    Returns: 8.350217011452761E12

  17. {0, 0, 2, 0, 3, 4, 4, 5, 1, 0, 6, 5, 1, 7, 11, 15, 0, 10, 18, 3, 7, 16, 0, 3, 4, 15, 0, 10, 24, 18, 26, 8, 18, 0, 3}

    {6566501, 6416191, 5140954, 1528921, 6330812, 3278728, 4334861, 8236767, 5236445, 5748058, 1942710, 3113531, 5049258, 998933, 3912512, 2400022, 4279628, 374940, 6157977, 2793660, 7388838, 9539946, 7191453, 7833481, 1727396, 9360915, 3873665, 1024488, 2482039, 970539, 1646566, 912235, 9585990, 6978826, 3142709, 330637}

    Returns: 6.317106301388139E12

  18. {0, 1, 2}

    {46879374, 18684677, 73327790, 80982840}

    Returns: 2.826110222620563E14

  19. {0, 0, 0, 2, 2, 1, 4, 7, 8, 2, 1, 11, 10, 5, 3}

    {4191839, 5607828, 8887016, 4552279, 24614, 8669370, 5947032, 9783950, 6273735, 1095029, 3091249, 2797889, 1827735, 9030792, 6806416, 7850103}

    Returns: 8.097115868697367E12

  20. {0, 0, 2, 2, 1, 2, 3, 2, 8, 5, 6, 10, 6, 1, 12, 14, 12, 1, 14, 9, 6, 5, 12, 20, 9, 14, 26, 8, 1, 5, 2, 28, 0, 14, 21, 34, 21, 28, 23, 35, 17, 40, 6, 26, 42}

    {661, 751, 832, 769, 387, 481, 910, 127, 488, 199, 871, 567, 679, 772, 239, 182, 118, 492, 409, 250, 589, 201, 143, 101, 998, 959, 317, 311, 561, 697, 517, 756, 750, 150, 890, 497, 506, 588, 583, 339, 164, 975, 45, 833, 685, 67}

    Returns: 69573.23653611536

  21. {0}

    {82648843, 88046661}

    Returns: 2.4280365967603335E12

  22. {0, 0, 0, 2, 4, 2, 1, 2, 5, 4, 9, 10, 2, 5, 12, 6, 11, 13, 16, 4, 0, 21, 22, 15, 21, 16, 26, 14, 5, 3, 15, 20}

    {28819184, 70559172, 38860502, 3238381, 57856460, 33004090, 99625004, 11067849, 13195024, 49799226, 48537285, 95184822, 58866145, 58104177, 80485008, 3550954, 86724529, 80660434, 58635422, 79475467, 49910929, 96766454, 76528817, 11262177, 62102585, 31829327, 20763806, 99981528, 3027081, 76954212, 6083548, 27511164, 30864135}

    Returns: 8.325876067471131E14

  23. {0, 1, 0, 3, 4, 4, 6, 4, 3, 1, 0, 5, 0, 10, 1, 2, 7, 1, 0, 13, 11, 17, 22}

    {19817, 49628, 30453, 80102, 12078, 58277, 89044, 93407, 24583, 42216, 46476, 46414, 20779, 89688, 73016, 40967, 33000, 24258, 37591, 97146, 28434, 74027, 60551, 84858}

    Returns: 7.098528968853588E8

  24. {0, 0, 2, 1, 3, 3, 5, 2, 4, 1, 10, 3, 2, 10, 13, 12, 2, 2, 4, 12, 7, 20, 14, 5, 23}

    {464183, 905356, 350102, 872271, 750817, 634686, 622744, 114210, 350209, 908450, 534407, 744590, 894870, 988600, 941278, 462900, 322945, 202511, 428247, 214237, 624729, 671344, 824812, 769195, 850860, 333463}

    Returns: 6.230652441756766E10

  25. {0, 1}

    {23884, 88141, 19406}

    Returns: 5.33218608787037E8

  26. {0, 0, 0, 0, 2, 1, 0, 4, 3, 4, 8, 3, 6, 10, 9, 10, 11, 15, 9, 5, 1, 0, 1, 15, 0, 7, 7, 23}

    {770, 761, 436, 42, 346, 987, 114, 500, 730, 791, 610, 418, 825, 456, 709, 903, 165, 183, 184, 465, 125, 914, 836, 913, 408, 641, 7, 954, 985}

    Returns: 85185.76259188724

  27. {0, 0, 0, 3, 4, 5, 2, 7, 6, 1, 7, 8, 12, 4, 8, 12, 14, 11, 17, 8, 15, 11, 17, 10, 3, 7, 5, 9, 8, 2, 27, 19, 32, 11, 23}

    {5064, 5282, 6121, 8030, 8605, 87, 7756, 4021, 2915, 2770, 9071, 8741, 820, 7288, 7462, 1466, 2266, 8610, 5997, 3764, 6520, 1928, 8645, 6307, 2272, 7835, 9590, 698, 5621, 5097, 2105, 4608, 9166, 2607, 3441, 5684}

    Returns: 7843245.426976454

  28. {0, 1, 1, 1, 1, 2, 6, 4, 5, 7, 10, 10, 10, 7, 10, 9, 11, 1, 0, 14, 4, 4, 11, 8}

    {421376024, 657859261, 89075382, 169488109, 198325091, 129073552, 981844548, 959522353, 257441743, 471831095, 589234015, 248672287, 606326903, 140097645, 53910432, 955719447, 966500133, 286228639, 592378280, 714991871, 10337572, 932074006, 228111258, 292146850, 163944594}

    Returns: 1.02171894910383328E17

  29. {0, 0, 1, 3, 0, 3, 4, 7, 6, 3, 9, 2}

    {8023, 5564, 7088, 1028, 9977, 4904, 5040, 4992, 7056, 4627, 8666, 8171, 7908}

    Returns: 6275383.005101668

  30. {0, 1, 0, 2, 4, 3, 5, 4, 1, 3, 0, 9, 6, 1, 3, 2, 6, 6, 8, 10, 0, 16, 9, 17, 22, 22, 22, 20, 28, 19, 0, 13, 29, 6, 9, 8, 24, 6, 23, 18, 13, 22, 31, 21, 27, 18, 17, 2}

    {594, 724, 999, 225, 233, 93, 561, 528, 203, 738, 164, 163, 972, 422, 943, 771, 981, 145, 746, 374, 50, 79, 546, 807, 386, 716, 538, 994, 809, 806, 162, 361, 723, 499, 648, 64, 671, 927, 661, 296, 21, 261, 498, 550, 650, 426, 656, 339, 524}

    Returns: 83623.00929527517

  31. {0, 0, 2, 2, 4, 2, 5, 1, 1, 6, 6, 4, 2, 7, 7, 15, 6, 1, 10, 16, 8, 19, 8, 8, 1, 20, 4, 18, 10, 27, 14, 31, 2, 8, 15, 17, 13, 24, 31, 32, 15, 20}

    {46164, 79982, 33088, 47983, 79983, 95202, 87068, 24929, 71468, 44826, 63487, 85231, 6550, 65063, 81134, 1052, 56497, 79180, 34629, 53186, 55050, 24645, 38073, 56289, 55462, 95709, 36905, 70335, 51244, 88739, 86850, 88166, 48517, 84782, 59462, 52238, 94849, 77664, 80403, 94651, 88691, 26845, 5130}

    Returns: 6.575195111798346E8

  32. {0, 1, 2, 2, 0, 5, 2, 5, 7, 6, 4, 2}

    {5983485, 6239188, 7952426, 4720827, 7348155, 9264116, 7217893, 3326638, 9678619, 3297804, 9309329, 4722596, 6123540}

    Returns: 2.8574790042109194E12

  33. {}

    {46717415}

    Returns: 0.0

  34. {0, 0, 0, 0, 2, 5, 5, 1, 1, 4, 3, 8, 8, 12, 12, 11, 11, 9, 14, 4, 1, 2, 9, 13}

    {45, 73, 33, 90, 61, 21, 60, 39, 16, 5, 24, 55, 86, 40, 76, 13, 75, 1, 99, 20, 52, 10, 34, 14, 74}

    Returns: 772.1588882347912

  35. {0, 0, 2, 3, 4, 0, 5, 7, 0, 7, 6, 11, 6, 11, 12, 15, 4, 14}

    {7784175, 645435, 4548561, 3665400, 3051668, 9610806, 8647396, 5427202, 6285921, 2490484, 14895, 1820219, 3409441, 1106240, 893351, 4479920, 6447141, 1779771, 4493310}

    Returns: 7.427277123996867E12

  36. {0, 1, 0, 1, 0, 3, 6, 7, 3, 4, 3, 0, 7, 10, 5, 6, 0, 8, 9, 3, 11, 11, 15, 5, 0, 1, 18, 16, 28, 0, 8, 15, 5, 29, 9, 29, 32, 14, 3, 7, 4, 11, 30, 27, 30, 33}

    {15, 83, 26, 63, 7, 88, 31, 84, 47, 94, 73, 45, 66, 79, 98, 75, 40, 35, 69, 18, 76, 53, 56, 28, 12, 4, 48, 49, 99, 14, 24, 11, 1, 90, 8, 68, 77, 93, 52, 89, 42, 67, 38, 57, 91, 72, 54}

    Returns: 834.1379177135949

  37. {0, 0, 1, 2, 4, 2, 0, 6, 3, 4, 8, 9, 10, 5, 1, 9, 7, 13, 18, 13, 9, 6}

    {491, 754, 399, 748, 837, 225, 750, 282, 102, 502, 957, 241, 858, 918, 881, 581, 466, 679, 89, 721, 548, 383, 65}

    Returns: 69554.21884996902

  38. {0, 1, 0, 0, 4, 0, 6, 6, 6, 6, 1, 7, 7, 9, 7, 1, 4, 17, 9, 17, 10, 2, 17, 23, 5, 15, 13, 22, 16, 14, 1, 26, 7, 16, 28, 25, 34, 24, 12, 26, 31, 39, 1}

    {887733, 475224, 173575, 182910, 989762, 410075, 635315, 15228, 303360, 324189, 20511, 643302, 378671, 88051, 88375, 263143, 511486, 108986, 576890, 602313, 929856, 368021, 127567, 225971, 798469, 910773, 531363, 887206, 86760, 998482, 124365, 685887, 161901, 172576, 60399, 105764, 122005, 580764, 527344, 624309, 665164, 31391, 561784, 489584}

    Returns: 8.87245797460811E10

  39. {0, 0, 2, 3, 0, 1, 1, 4, 7, 2, 1}

    {4838904, 6708914, 8454353, 4576912, 4206910, 4113198, 2386585, 7387332, 8207556, 4580229, 9580667, 3004363}

    Returns: 3.7232601290122666E12

  40. {0, 0, 2, 2, 3, 2, 1, 2, 2, 2, 9, 6, 2, 4, 2, 12, 2, 8, 10, 18, 1, 13, 19, 8, 4, 1, 25, 6, 10, 27, 30, 15, 18, 7, 20}

    {595547, 281281, 981916, 513888, 187043, 234158, 514200, 682425, 22936, 968112, 240181, 954439, 788975, 798988, 204913, 356888, 316729, 26739, 688711, 402104, 190583, 151576, 918404, 58923, 854708, 768037, 595128, 820385, 296358, 844786, 285420, 509789, 168650, 344772, 231544, 753902}

    Returns: 8.79494801664219E10

  41. {0, 0, 1, 3, 2, 2, 4, 4, 6, 8, 5, 8, 8, 12, 10, 0, 9, 8, 1, 19, 15, 2, 9, 8, 13, 17, 8, 26, 22, 8, 8, 6, 31, 13, 9, 5, 2, 37, 22, 0, 36, 9, 32, 41, 27, 24}

    {644, 490, 315, 875, 656, 978, 177, 354, 63, 230, 892, 300, 612, 306, 858, 286, 155, 205, 456, 239, 476, 223, 909, 482, 298, 854, 326, 745, 100, 640, 199, 724, 528, 806, 221, 539, 911, 110, 104, 137, 651, 940, 258, 173, 879, 614, 609}

    Returns: 77878.58391711769

  42. {0, 1, 0, 2, 0, 1, 6, 0, 7, 8, 1, 7, 2, 12, 6, 12, 7, 16, 6, 7, 6, 10, 11, 11, 9, 9, 4, 24, 26, 23, 2, 18, 1, 19, 32, 23, 19, 19, 22}

    {569870472, 716785465, 271987838, 889563866, 498461964, 599999175, 725527189, 675734605, 373567561, 884163922, 648149625, 823363564, 197474118, 637362194, 851256170, 313632008, 286069730, 641229128, 770948415, 635176243, 931210284, 601468714, 18354574, 278189470, 635249496, 345825044, 982014167, 80977628, 592733213, 705157048, 577066171, 344833108, 675123764, 473730533, 471737590, 105564622, 490997315, 808541121, 145088098, 322134713}

    Returns: 5.4734613731152912E16

  43. {0, 0, 1, 0, 2, 5, 2, 7, 0, 2, 7, 9, 6, 4, 1, 10, 2, 8, 8, 19, 13, 9, 6, 14, 4, 9, 14, 7, 11, 8, 15, 5}

    {686, 802, 122, 755, 724, 471, 158, 645, 96, 903, 922, 541, 697, 998, 953, 315, 753, 50, 466, 412, 946, 822, 504, 563, 548, 239, 123, 329, 786, 652, 613, 571, 558}

    Returns: 76515.89724051971

  44. {0, 1, 1, 3, 0, 4, 3, 1, 5, 3, 2, 7, 12, 12, 4, 0, 16, 9, 7, 18, 8, 17, 5, 13, 20, 6, 14, 24, 26, 6, 2, 16, 7, 30, 19, 9}

    {268202, 9935328, 6738234, 3837464, 1474250, 2844439, 121905, 1004702, 9511475, 3140181, 1795885, 3161848, 7969026, 5613356, 5754009, 9907703, 3402941, 5470764, 2428254, 8310902, 4738286, 6877025, 3548411, 3687033, 4430400, 5580208, 4568411, 1122554, 3303586, 6964042, 3772386, 6711659, 3118714, 3107182, 4788371, 1794940, 7501997}

    Returns: 7.94960753870268E12

  45. {0, 1, 1, 2, 1, 2, 4, 3, 7, 8, 2, 5, 9, 5, 2}

    {8507, 1500, 1615, 973, 360, 3056, 428, 142, 9482, 4610, 4900, 1655, 3157, 841, 9944, 8490}

    Returns: 9414228.453740638

  46. {0, 1, 2, 1, 1, 5, 2, 1, 0, 6, 4, 3}

    {900, 632, 473, 173, 564, 303, 123, 778, 75, 334, 199, 915, 997}

    Returns: 68673.14425423002

  47. {0, 1, 2, 2, 4, 1, 1, 5, 1, 0, 3, 5, 4, 5, 0, 7, 4, 10, 15, 12, 14, 1, 0, 18, 15, 23}

    {778, 759, 848, 972, 686, 725, 509, 236, 522, 373, 342, 249, 37, 442, 744, 511, 642, 15, 112, 683, 440, 780, 518, 701, 598, 20, 621}

    Returns: 66500.36054102362

  48. {0, 1, 1, 1, 3, 0, 6, 2, 7, 3, 4, 7, 4, 2, 12, 1, 5, 15, 15, 8}

    {89589247, 79564159, 94201960, 8041834, 93372081, 98645414, 86670974, 39442072, 93145126, 31599186, 28281981, 57005657, 19362378, 30588674, 85391059, 82701841, 98599533, 12619483, 38290801, 98533398, 8870035}

    Returns: 1.0250715534042224E15

  49. {0, 1, 2, 2, 3, 2}

    {930691476, 177131139, 950774499, 586613721, 131491889, 3647781, 741543290}

    Returns: 9.6232325353895408E16

  50. {0, 1, 0, 3, 1, 3, 6, 7, 0, 8, 9, 7, 12, 2}

    {22886867, 82704414, 93887278, 82534042, 44059480, 44291913, 35195042, 35007212, 95950722, 31910519, 88822376, 30780992, 95707548, 16238348, 13818041}

    Returns: 7.813227932789256E14

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

    {94062048, 45705595, 27731116, 30203017, 97180070, 33336426, 98127440, 50812916, 22873208, 647851, 14869403, 45902210, 33961444, 33335108, 17880526, 56176205, 9581016, 74572423, 48015032, 53841779, 66508588, 1945738, 72673140, 49540906, 35225487, 77010468, 57737858, 61226874}

    Returns: 8.022680321251778E14

  52. {0, 0, 0, 0}

    {98, 69, 40, 34, 42}

    Returns: 503.6973472222222

  53. {0, 1, 1, 0, 0, 5, 5, 7, 1, 9, 5, 2, 6, 6, 6}

    {358967, 532345, 298550, 476433, 342916, 710414, 704460, 57930, 74292, 901588, 444929, 802315, 856078, 29428, 908474, 128352}

    Returns: 7.259856363349802E10

  54. {0, 0, 0, 2, 1, 3, 2, 7, 4, 1, 5, 1, 3, 10, 2, 5, 15, 11, 2, 2, 20, 9, 8, 23, 6, 4, 17, 22, 12, 9, 26, 3, 12, 8, 0, 22, 18, 27, 5, 16, 13, 8, 28, 15, 32, 4}

    {42, 55, 46, 76, 16, 23, 73, 96, 78, 14, 69, 11, 59, 68, 30, 83, 99, 94, 38, 24, 31, 21, 67, 43, 25, 13, 63, 81, 75, 98, 37, 35, 7, 5, 58, 47, 33, 17, 48, 53, 77, 52, 100, 39, 80, 49, 10}

    Returns: 753.1669438173865

  55. {0, 0, 0, 3, 2, 4, 3, 1, 8, 5, 9, 3, 1, 11, 6, 14, 10, 13, 15, 4, 8, 14, 6, 6, 23}

    {350294, 846101, 140659, 296791, 736462, 47230, 724855, 39217, 499094, 491270, 110132, 704100, 273101, 650585, 241342, 888428, 318332, 255465, 818316, 284769, 927013, 432600, 745496, 681215, 608188, 69339}

    Returns: 6.960734604132059E10

  56. {0, 1, 1, 3, 1, 1, 2, 7, 7, 1, 5, 4, 7, 12, 5, 12, 9, 16, 10, 15, 20, 13}

    {16762700, 45239737, 81626221, 48490261, 66170223, 21651216, 61041900, 48946187, 61327462, 79369954, 4441596, 9193571, 55670282, 65606106, 72265184, 6538044, 99085908, 39111882, 9675769, 54376056, 68774770, 93827570, 54937049}

    Returns: 6.406441876867949E14

  57. {0, 0, 2, 0, 2, 2, 6, 1, 8, 1, 9, 0, 1, 4, 14, 12, 10, 5, 15, 18}

    {88990148, 34855336, 55566105, 58475509, 59347349, 1698630, 29908107, 13086500, 77727194, 45241373, 94433521, 14470250, 61207172, 15803497, 70489877, 79071015, 40384549, 47291337, 27269867, 61649712, 26097507}

    Returns: 6.52170914335565E14

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

    {17726, 25440, 6253, 43157, 54584, 67117, 62984, 71566, 6498, 12889, 80012, 34039, 26897, 82318, 51933, 5450, 54532, 92670, 78325, 1656, 10557, 68036}

    Returns: 7.214505576027356E8

  59. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {70, 46, 75, 85, 71, 63, 6, 94, 4, 91, 60, 42, 36, 47, 83, 55}

    Returns: 606.1975671114942

  60. {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1}

    {991117, 511138, 105954, 202714, 120876, 409405, 147449, 387446, 602038, 453553, 563575, 799228, 734543, 509423, 245914, 222422, 769789, 244492, 133622, 967584, 772724}

    Returns: 7.924725549892552E10

  61. {0, 0, 0, 1, 2, 0, 3, 0}

    {8492, 5290, 4638, 3683, 4103, 9970, 1464, 2547, 9667}

    Returns: 6163132.720229294

  62. {0, 0, 0, 0, 0, 2, 2, 0, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 0, 2, 1, 0, 0, 2, 1, 1, 0, 1, 2, 2, 0, 0, 0, 0, 0, 2, 2, 2, 1, 2, 0}

    {17979951, 6658730, 37002135, 29003251, 94441870, 38590971, 17220010, 61427921, 46244033, 73797151, 93030820, 55828734, 94964924, 79315702, 35227486, 85717656, 40712892, 28422966, 99413084, 32334067, 43566464, 71576486, 40729919, 96279472, 67759190, 37177047, 33175043, 94351602, 2265879, 95839209, 90371720, 8830239, 48774892, 52690996, 80859034, 96480677, 60433451, 68668064, 11084274, 8650711, 77613089, 67117986, 49453505, 62052180, 58214570, 74591228, 40074943, 92594707, 63918163, 79640925}

    Returns: 8.114740217311689E14

  63. {0, 1}

    {2849355, 1578455, 5848329}

    Returns: 1.3610487056809814E12

  64. {0, 0, 0, 0, 4, 1, 2, 3, 4, 2, 4, 1, 1, 2, 1, 3, 1, 0, 1, 1, 1, 0, 0, 2, 0, 4, 1, 0, 3, 1, 4, 4, 3, 4, 0, 3, 2}

    {231, 744, 26, 20, 643, 286, 449, 15, 971, 822, 380, 687, 701, 415, 93, 431, 901, 3, 291, 796, 287, 980, 605, 79, 255, 188, 839, 282, 653, 655, 187, 978, 336, 408, 786, 355, 400, 961}

    Returns: 92745.28220235664

  65. {0, 0, 2, 2, 2, 3, 3, 1, 3, 3, 0, 4, 4, 4, 4, 4, 4, 0, 0, 1, 1, 1, 1, 0, 2, 4}

    {68, 86, 81, 17, 51, 54, 70, 63, 44, 29, 65, 58, 74, 79, 97, 66, 45, 62, 35, 60, 21, 40, 87, 84, 36, 4, 38}

    Returns: 532.5086465412039

  66. {0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0}

    {52, 61, 65, 7, 46, 80, 39, 22, 72, 77, 93, 29, 57, 20, 100, 48}

    Returns: 547.309719074653

  67. {0, 1, 1, 0, 1, 1, 1, 0, 3, 4, 0}

    {42, 13, 46, 48, 69, 98, 56, 17, 44, 28, 4, 99}

    Returns: 694.5728077353879

  68. {0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 0, 1, 1}

    {8862, 3118, 8654, 4669, 8601, 7310, 488, 6986, 8322, 2356, 1228, 896, 4380, 7345, 3715, 7501, 4786, 595, 9677, 7628, 4506, 731, 7252, 5772}

    Returns: 8452396.8510623

  69. {0, 1, 2, 3, 0, 1, 6, 3, 4, 7, 10, 8, 12, 12, 12, 12, 14, 15, 17, 18, 17, 18, 18, 22, 21, 24, 25, 23, 24, 28, 27, 28}

    {57034370, 22175375, 56610601, 81822620, 27423194, 34336466, 27303225, 4798018, 1616496, 7355392, 16915145, 55103879, 71503210, 55614090, 99978105, 29838911, 59610468, 6956318, 93794741, 24123995, 59273094, 16688675, 96078672, 51406565, 44998745, 49322056, 19167336, 58802191, 18823157, 11015937, 15460295, 97680968, 9722645}

    Returns: 9.273715185728046E14

  70. {0, 1, 2, 2, 4, 4, 6, 7, 7, 9, 10, 10, 12, 13, 13, 15, 16, 16, 17, 19, 19, 20, 21, 23, 23, 24, 25, 27, 28}

    {12, 3, 46, 36, 94, 79, 84, 76, 21, 35, 54, 26, 14, 68, 23, 90, 8, 61, 80, 34, 65, 6, 49, 100, 42, 70, 25, 87, 62, 92}

    Returns: 863.59469140958

  71. {0, 0, 1, 2, 2}

    {1827, 1973, 6785, 1256, 4275, 4864}

    Returns: 2342765.087696759

  72. {0, 1, 2, 3}

    {29962, 90693, 96821, 10453, 63099}

    Returns: 7.272398089418334E8

  73. {0, 0, 2, 0, 3, 0, 4, 7, 4, 4, 10}

    {19684, 26763, 9902, 8063, 42302, 27803, 11996, 73430, 73645, 63798, 56863, 73783}

    Returns: 4.44263365360435E8

  74. {0, 1, 2, 1, 3, 2, 6, 6, 4, 9, 10, 11, 12, 13, 12, 12, 14, 14, 15, 15, 20, 21, 19, 21}

    {603948491, 121539949, 450100621, 2928409, 654402938, 786008273, 342435114, 987641334, 391989735, 13180994, 789250809, 436436853, 662784334, 847649915, 774017180, 154222410, 328000546, 893682926, 523124638, 337313306, 527879731, 414191932, 423652742, 333386044, 487128583}

    Returns: 6.72447161795882E16

  75. {0, 1, 2, 2, 4, 5, 5, 6, 7, 9, 9, 10, 11, 13, 13, 14, 15, 17, 18, 19, 19, 21, 21, 22, 23, 24, 26, 26, 28, 28, 29, 31, 31}

    {703263328, 2305303, 887123269, 834610013, 807156103, 253297812, 958059542, 635979091, 555535684, 592237714, 634157942, 313875959, 913253006, 847858702, 962011085, 748503000, 699907877, 74192210, 528997594, 639624639, 302610226, 436119167, 651830275, 951403502, 236929965, 364939022, 75925039, 963227120, 475558198, 839458133, 524194050, 920187581, 718982165, 80284274}

    Returns: 7.7169609443979264E16

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

    {51530267, 61549767, 38062046, 74149393, 35461691, 24320093, 89677464, 22046563, 48889982, 25077586, 16128902, 53888417, 52158660, 84926938, 19104976, 77265165, 84340165, 55359459, 12548146, 72833461}

    Returns: 5.1211047402104075E14

  77. {0, 1, 2, 2, 4, 5, 3, 7, 6, 8, 9, 11, 10, 12, 14, 14, 14, 15, 16, 16, 17, 19, 21, 21, 21, 23, 24, 27, 25, 28, 27, 29, 32, 31, 33, 34, 34, 34, 37, 37, 37, 40, 39, 43}

    {42419940, 53061086, 13355901, 76298825, 38629946, 81489223, 33628769, 48139128, 81129818, 74460731, 82271638, 19131125, 91094395, 39070554, 45602331, 70262833, 8430474, 9202821, 46262248, 67761247, 22863404, 96362668, 79557075, 98498059, 50921579, 70292853, 20101958, 72973020, 21562347, 25641418, 52206550, 50710772, 62204662, 74982969, 40348984, 26359581, 94384040, 40425147, 51923830, 64825202, 91811499, 40191283, 1445819, 40058381, 62678529}

    Returns: 7.041506579874241E14

  78. {0, 0, 1, 0, 0, 5, 2, 3, 6, 8, 8, 8, 8, 12, 10}

    {33441, 14760, 30875, 81355, 37832, 3481, 56929, 22130, 16448, 77408, 89094, 71662, 56378, 44506, 87202, 16212}

    Returns: 7.233170514628494E8

  79. {0, 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 }

    {999999999, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 0.0022541745919277614

  80. {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 0.0

  81. {0, 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}

    {999999999, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}

    Returns: 0.0022541745919277614

  82. {0, 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}

    {1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

    Returns: 0.0022541745919277614

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: