Statistics

Problem Statement for "WhichData"

Problem Statement

You have just received a int[] sampleData from the laboratory. You know that the variance of this data should be varNum/varDen, where varNum and varDen are ints. Note that varNum/varDen need not be an integer. Your method will return which nonempty subset of the elements from sampleData produces a variance closest to the variance you expected. This subset may be the entire sampleData. The variance of a subset of the sampleData can be calculated via the following formula. Let s(i) denote the ith element of the subset (assuming some method of indexing into the subset), and let n denote the size of the subset. Then 
     mean = ( s(0) + s(1) + s(2) + ... + s(n-1) )/n
     varsum = (mean-s(0))^2 + (mean-s(1))^2 + ... + (mean-s(n-1))^2
     variance = varsum/n
The subset will be returned as a int[], whose elements are the values of the subset, sorted in nondescending order. If two subsets are equally far from the expected variance, choose the one whose return value comes first lexicographically. A int[] X comes lexicographically before a int[] Y if there is a position j such that, X[i]=Y[i] for all i<j, and X[j]<Y[j]. If X is a proper prefix of Y, it occurs lexicographically before it.

Definition

Class:
WhichData
Method:
bestVariance
Parameters:
int[], int, int
Returns:
int[]
Method signature:
int[] bestVariance(int[] sampleData, int varNum, int varDen)
(be sure your method is public)

Notes

  • doubles will provide enough precision to properly solve this problem. Given two subsets, s1 and s2, the difference between |variance(s1)-varNum/varDen| and |variance(s2)-varNum/varDen| will be either 0, or greater than 1e-9, where variance(x) is the variance of subset x.

Constraints

  • varNum will be between 0 and 10000 inclusive.
  • varDen will be between 1 and 10000 inclusive.
  • sampleData will contain between 2 and 16 elements inclusive.
  • Each element of sampleData will be between -10000 and 10000 inclusive.

Examples

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

    40

    20

    Returns: { 1, 2, 3, 4, 5 }

    The variance should be 40/20 = 2. The set of numbers {1,2,3,4,5} has mean = (1+2+3+4+5)/5 = 3 varsum = 2^2 + 1^2 + 0^2 + 1^2 + 2^2 = 10 variance = 10/5 = 2

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

    20

    40

    Returns: { 1, 2, 3 }

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

    9

    1

    Returns: { 1, 7 }

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

    6

    1

    Returns: { 1, 2, 4, 5, 8 }

  5. {-10000,10000,-9999,9999,-9998,9000}

    10000

    1

    Returns: { -10000, -9998 }

  6. {-10000,10000,-9999,9999,-9998,9998,1,1,2,2}

    9999

    10000

    Returns: { -10000, -9998 }

  7. {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, 10000,10000,10000,10000,10000,9999}

    500

    10000

    Returns: { 9999, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

  8. {500,500,500,500,500,500,500,580, 100,100,100,100,100,100,100,180}

    700

    1

    Returns: { 100, 100, 100, 100, 100, 100, 100, 180 }

  9. {100,100,100,140, 200,200,200,240, 300,300,300,340, 9900,9900,9900,9939}

    3218

    11

    Returns: { 9900, 9900, 9900, 9939 }

  10. {100,100,100,140, 200,200,200,240, 300,300,300,340, 9900,9900,9900,9939}

    3219

    11

    Returns: { 100, 100, 100, 140 }

  11. {500,500,500,500,500,500,500,581, 100,100,100,100,100,100,100,180}

    7797

    11

    Returns: { 500, 500, 500, 500, 500, 500, 500, 581 }

  12. {500,500,500,500,500,500,500,581, 100,100,100,100,100,100,100,180}

    7796

    11

    Returns: { 100, 100, 100, 100, 100, 100, 100, 180 }

  13. {10,10,10,10,10,10}

    0

    9999

    Returns: { 10 }

  14. { 43, 67, 81, 89, 90, 70, 71, 76, 92, 99, 8, 15, 16, 23, 34, 36 }

    8435

    584

    Returns: { 67, 70, 76 }

  15. {-8125,-7919,-7820,-5898,547,1831,3110,6871,8950,8970,9803}

    841

    111

    Returns: { -8125 }

  16. {-9875,-9522,-6753,-6583,-4146,-2589,-320,-291,-230,1669,2681,4329,4500,6656,8470,9816}

    8932

    14

    Returns: { -291, -230 }

  17. {-7169,-6806,-5307,-4197,-3863,-298,-70,2344,3337,5932,6846,7857,8503,8523,9168}

    8059

    216

    Returns: { -7169 }

  18. {-7695,-7065,-6323,-5973,-5961,-3926,-3684,-161,582,763,863,1469,2110,5797,8738}

    672

    13

    Returns: { -5973, -5961 }

  19. {-8530,-7566,-6171,-5831,-3499,-2120,612,2073,2354,7188,9605,9619}

    4553

    118

    Returns: { 9605, 9619 }

  20. {-7631,-7630,-6311,-6070,-3384,-3363,-1131,850,2313,4735,6471,7141,9484}

    8349

    1

    Returns: { -6311, -6070 }

  21. {-9750,-8118,-7486,-5570,-5568,-4692,-3558,-3144,1863,3613,8284,8313,8377,8547}

    1100

    2309

    Returns: { -9750 }

  22. {-2602,-2572,-1417,1081,1746,2441,2572,2762,3039,4307,4351,5946,9946}

    9212

    37

    Returns: { -2602, -2572 }

  23. {-7316,-6148,-4041,-4032,-3656,-3625,-3339,-2185,-2096,2387,4823,6171}

    5358

    541

    Returns: { -7316 }

  24. {-9884,-8792,-8772,-5223,-4039,-3226,-1832,-1610,3384}

    6570

    81

    Returns: { -8792, -8772 }

  25. {-7581,-5509,-4619,1198,2062,2634,2684,3903,5225,6463,7279,8070,8928}

    8661

    6

    Returns: { 2634, 2684 }

  26. {-8513,-5539,-4769,-4115,-294,-186,2880,3524,7345,8316,8665,8830,9055,9608}

    7613

    3

    Returns: { -294, -186 }

  27. {-4725,-1248,-122,338,730,2992,3005,4424,7061}

    8798

    430

    Returns: { -4725 }

  28. {-9131,-7815,-500,1837,1840,5209,5777,5846}

    2378

    2160

    Returns: { -9131 }

  29. {-7193,-6606,-6597,413,1121,3145}

    3399

    245

    Returns: { -6606, -6597 }

  30. {-9834,-8679,-1911,-1748,-167,-122,2204,4296,5599,6279,6412}

    6069

    23

    Returns: { -167, -122 }

  31. {-9529,-9490,-7898,-6553,-3226,-459,1612,2481,3265,4682,5923,7236,7814,8715}

    6722

    32

    Returns: { -9529, -9490 }

  32. {-8942,-8070,-7791,-6036,-2643,-1039,-231,175,3243,6773,6785,6885,8451}

    7250

    429

    Returns: { -8942 }

  33. {-9975,-8164,-5966,-3162,5212,5767,6473,6563,8330,9978}

    2046

    102

    Returns: { -9975 }

  34. {-7672,-7319,-6345,-3238,-632,-618,2692,5490,8850,9112,9228}

    2386

    158

    Returns: { -7672 }

  35. {-7492,-7489,-6882,-4460,-3054,3940,4656,6521,6611,9826}

    8250

    7383

    Returns: { -7492 }

  36. {1397,-6457,1395,9154,-696}

    1178

    2157

    Returns: { 1395, 1397 }

  37. {7493,-9819,7540,227,5117,-8095,9251}

    6805

    108

    Returns: { -9819 }

  38. {8402,629,4277,7254,15,-3136,8069,-8165,-6536,-8749,6818,7238}

    8164

    327

    Returns: { -8749 }

  39. {-5362,-2101,4197,-8132,5752,8854,-1919,2003,-2722,-1909,7388,-6989,-6945}

    3857

    238

    Returns: { -1919, -1909 }

  40. {4638,8862,1898,8469,-9854,-3392,1886,6042,-367,7372,-6138,-7924,5519,4153}

    6520

    426

    Returns: { -9854 }

  41. {2408,-4773,-2211,-735,8215,7173,-8882,995,-6547,6289,4178,7598,-2711,-2247,1580}

    9434

    5

    Returns: { -2247, -2211 }

  42. {5168,8048,-9627,-4845,-704,6234,2739,-7735,6551,-2353,9945,-5746,2878,4090,5145,-3759}

    1656

    108

    Returns: { -9627 }

  43. {4789,522,8450,1104,2795,2647}

    7107

    2

    Returns: { 2647, 2795 }

  44. {340,7008,7796,7019,-2575,-1435,-6959,-1653,-962,-9540,2780,187,5794,-2918,-5654,4271}

    9481

    706

    Returns: { -9540 }

  45. {-7504,-6776,2087,7132,-2949,-2544,8022,455,7148,6980,-3534,2579,6693,-8717,-566}

    9446

    375

    Returns: { -8717 }

  46. {-218,5470,-3212,855,-5485,-6353,3443,9156,9151,-1450,-1845,5033,5808,-260}

    9200

    3037

    Returns: { -6353 }

  47. {-2593,2204,4823,951,-6662,-7662,-2714,9048,5071,9838,-9351,9792,-2859,5815}

    9085

    17

    Returns: { 9792, 9838 }

  48. {3580,-5908,-8215,2378,-6539,4933,6754,1569,5542,-3408,-7609,1587,-8672,-7099,7114}

    9057

    274

    Returns: { -8672 }

  49. {4301,4095,-6384,-3717,9355,-6611,-2634,9764,9395,-2074,-6622,-8489,235,1837,-7194,4577}

    9160

    38

    Returns: { 9355, 9395 }

  50. {9463,9131,-6764,-1358,-9738,-2545,4117,9459,-9191}

    5702

    2917

    Returns: { -9738 }

  51. {8381,4407,-854,-200,9096,5675,4383,2081,487}

    6966

    137

    Returns: { -854 }

  52. {-8198,-6374,-6942,8334,7326,-5553,3990,-6518,7401,-4568,-9106,7458}

    2392

    105

    Returns: { -9106 }

  53. {9120,-7565,-7574,-6804,-1406,6573,5721,-8233,2075,-2790}

    9192

    821

    Returns: { -7574, -7565 }

  54. {747,7407,-1212,-2835,9491,-3855,-7362,-9422,769,-6652}

    5886

    3

    Returns: { 747, 769 }

  55. {8233,-3413,-6821,-3640,-3398,1082,224,8379,-2334,714,-7200,8582,-6445,-7299}

    6138

    196

    Returns: { -3413, -3398 }

  56. {-9922,-3876,9654,-6113,8173,-3034,-2985,7188,7965}

    7845

    120

    Returns: { -9922 }

  57. {-9302,4598,381,-4305,1886,-3186,9760,-8221,1305,-3258,-9278,-2938,5185,-9175,-770,8458}

    4685

    110

    Returns: { -9302 }

  58. {4562,9580,8440,9065,-8210,2228,-5029,4792,-8202,6064,-5482,-562,9427,4571,3417}

    2446

    91

    Returns: { 4562, 4571 }

  59. {-5682,-8016,-6493,-8884,-5533,-6528,-1753,-4831,1004,-199,-5676,9083,9660,-3583}

    305

    127

    Returns: { -8884 }

  60. {6256,5835,-9859,6081,-5656,-6494,5891,4404,2758,9897,-6674,8080,-2813,-3643}

    5165

    11

    Returns: { 5835, 5891 }

  61. {10,10,10,10,10,10,10,10, -10,-10,-10,-10,-10,-10,-10,-10}

    10000

    1

    Returns: { -10, -10, -10, -10, -10, -10, -10, -10, 10, 10, 10, 10, 10, 10, 10, 10 }

  62. {1,-14,13,15,-9,-6,-7,-5,10,9,9,-8,12,3,-10,-3}

    5452

    136

    Returns: { -14, -10, -9, -8, -7, -6, -5, -3, 1, 10 }

  63. {4,5,-11,-4,-2,-5,12,9,13,2,-7,0,10,-1,-14,-13}

    9959

    155

    Returns: { -14, -13, -11, -7, -5, -4, -2, 2, 9, 10 }

  64. {-1,2,1,10,8,12,-5,-1,12,2,4,-14,-3,-8,-2,0}

    9592

    130

    Returns: { -14, -8, -5, -3, -1, -1, 8, 10, 12, 12 }

  65. {5,-8,0,-2,13,0,0,8,-8,0,8,-8,-9,1,3,13}

    6280

    165

    Returns: { -8, -8, -2, 0, 0, 0, 1, 3, 8, 8, 13 }

  66. {4,1,3,11,0,-10,-4,-1,0,-12,3,12,-4,0,-5,-4}

    8407

    406

    Returns: { -5, -4, -4, -4, -1, 0, 0, 0, 1, 3, 12 }

  67. {-7,-2,0,-10,6,8,9,1,12,1,-13,9,-8,-10,8,10}

    2023

    57

    Returns: { -10, -2, 0, 1, 1, 6, 8, 8, 9, 10 }

  68. {3,-11,13,14,9,-1,-2,6,8,12,6,-4,6,11,-14,-5}

    4378

    76

    Returns: { -11, -5, -4, -2, -1, 6, 6, 6, 9, 13, 14 }

  69. {13,2,12,4,12,8,9,-13,3,-1,0,8,9,8,-11,-7}

    4238

    275

    Returns: { 0, 2, 4, 8, 8, 8, 9, 9, 12, 13 }

  70. {-12,-4,-10,0,-11,-7,-2,-12,4,10,-5,-2,0,-3,5,6}

    3537

    151

    Returns: { -11, -10, -7, -5, -4, -3, -2, -2, 0, 4, 5 }

  71. {-8,-5,7,-4,4,-5,12,14,7,-3,1,5,-1,-9,-1,0}

    2677

    45

    Returns: { -9, -8, -5, -5, -3, -1, -1, 7, 12, 14 }

  72. {13,6,1,-13,15,-7,13,0,15,-3,11,15,2,0,-12,15}

    4154

    35

    Returns: { -13, -12, -3, 6, 13, 13, 15, 15, 15, 15 }

  73. {2,5,8,15,-14,0,-2,3,0,-10,-3,-9,6,-13,4,-1}

    5787

    170

    Returns: { -14, -10, -3, -1, 0, 0, 2, 3, 4, 5 }

  74. {0,-14,10,-11,5,6,5,14,-4,-9,-1,7,-14,5,3,-5}

    5531

    76

    Returns: { -14, -14, -11, -9, -4, 3, 5, 5, 5, 6, 10 }

  75. {2,12,-11,13,1,0,0,3,-8,12,0,-4,0,-2,13,10}

    4512

    129

    Returns: { -11, -8, -4, -2, 0, 0, 0, 1, 2, 3, 13 }

  76. {5,14,2,-14,-4,8,12,-12,15,-12,13,14,0,12,0,10}

    3794

    44

    Returns: { -14, -12, -4, 0, 0, 2, 5, 8, 13, 14, 14 }

  77. {10,-7,12,-2,-5,8,2,13,-5,6,15,5,-3,-5,1,2}

    7219

    122

    Returns: { -7, -5, -5, -5, 1, 2, 5, 8, 12, 13, 15 }

  78. {5,5,6,11,9,6,5,-8,4,-11,13,12,3,-14,1,-14}

    8957

    864

    Returns: { 3, 4, 5, 5, 5, 6, 6, 9, 12, 13 }

  79. {-14,-3,-1,10,-5,0,13,6,11,9,5,6,3,-2,0,2}

    5061

    225

    Returns: { -5, -3, -2, -1, 0, 2, 5, 6, 6, 11 }

  80. {-14,1,-11,-4,8,-2,2,-10,-5,-13,-8,0,2,4,-12,10}

    6296

    101

    Returns: { -14, -13, -12, -11, -10, -5, -4, 0, 1, 2, 8, 10 }

  81. {11,0,-2,-9,6,4,7,-4,-2,8,-11,-5,8,-4,2,10}

    9276

    183

    Returns: { -11, -9, -4, -4, -2, 0, 2, 6, 8, 8, 10, 11 }

  82. {-11,6,10,6,8,10,-4,15,11,14,0,-10,15,-3,3,9}

    9120

    165

    Returns: { -10, -4, 0, 6, 6, 8, 9, 10, 11, 15, 15 }

  83. {4,-13,2,-2,-4,8,-13,5,9,2,0,-4,5,-10,-1,-1}

    8831

    257

    Returns: { -13, -10, -4, -4, -2, -1, 2, 4, 5, 5 }

  84. {4,-5,7,6,11,0,6,3,12,1,8,-14,0,-3,5,11}

    7322

    142

    Returns: { -14, -5, -3, 0, 0, 4, 5, 6, 7, 8, 11, 11, 12 }

  85. {0,11,13,14,2,-13,14,11,10,0,11,4,-7,-5,-7,0}

    9888

    183

    Returns: { -7, -7, 0, 0, 2, 10, 11, 11, 11, 13 }

  86. {7,-9,-3,0,3,-12,3,-6,6,2,-8,-7,-12,8,14,-6}

    8069

    114

    Returns: { -12, -12, -9, -8, -7, -6, -3, 2, 7, 8, 14 }

  87. {3,-7,-14,5,-13,10,1,-13,7,-9,-5,7,2,1,-3,0}

    9845

    198

    Returns: { -14, -13, -9, -7, -5, -3, 0, 1, 3, 5, 7, 7 }

  88. {0,-10,0,1,-8,-3,9,-2,-12,12,-9,-6,-13,-9,8,14}

    3723

    155

    Returns: { -13, -12, -10, -9, -9, -6, -3, -2, 0, 0, 1 }

  89. {6,4,6,10,-4,9,12,0,12,15,0,6,-6,8,-3,11}

    6274

    174

    Returns: { -6, -4, -3, 0, 0, 4, 6, 6, 6, 11, 12, 12 }

  90. {3,7,4,-8,1,0,8,-8,4,-1,-8,0,0,-13,10,-6}

    5277

    429

    Returns: { -1, 0, 0, 0, 1, 3, 4, 4, 8, 10 }

  91. {-10,7,-11,0,-4,0,12,5,-13,-9,-5,-5,-10,-4,-8,0}

    6349

    228

    Returns: { -13, -11, -10, -10, -9, -8, -5, -4, 0, 5 }

  92. {-1,5,2,-13,12,2,8,8,-14,8,13,10,14,8,0,15}

    7598

    336

    Returns: { -1, 0, 2, 2, 5, 8, 8, 8, 10, 15 }

  93. {0,-5,0,-4,0,-8,-4,0,-5,-7,-14,12,4,-3,-4,-7}

    9638

    761

    Returns: { -8, -7, -7, -5, -5, -4, -4, 0, 0, 0, 0, 4 }

  94. {-6,-9,-1,7,14,-5,4,1,3,-12,8,-3,-14,4,-5,8}

    5610

    89

    Returns: { -14, -12, -9, -1, 1, 4, 4, 7, 8, 8 }

  95. {-14,4,-11,-9,-9,7,-11,-11,-5,5,-5,-2,-7,-9,12,1}

    7803

    275

    Returns: { -11, -9, -9, -7, -5, -5, -2, 1, 4, 5 }

  96. {-7,4,-10,-8,-3,-12,6,4,10,-14,-10,-9,7,-6,10,2}

    9272

    140

    Returns: { -14, -12, -10, -10, -6, -3, 2, 4, 6, 7, 10 }

  97. {15,9,0,12,12,-9,-7,0,7,1,14,-9,8,-13,3,10}

    8254

    210

    Returns: { -7, 0, 0, 3, 7, 8, 9, 10, 12, 12, 15 }

  98. {-9,2,-1,3,-5,6,6,-7,13,-12,-10,5,-11,7,-2,13}

    9922

    132

    Returns: { -12, -11, -10, -9, -7, -2, -1, 2, 6, 6, 13, 13 }

  99. {9,1,1,5,-10,2,3,14,4,11,0,14,-7,2,-13,-12}

    8231

    143

    Returns: { -13, 1, 2, 2, 3, 5, 9, 11, 14, 14 }

  100. {-5,-8,-4,6,14,-12,-14,-12,0,-3,-5,-8,-5,-5,15,10}

    3237

    133

    Returns: { -14, -12, -8, -8, -5, -5, -5, -5, -4, -3, 6 }

  101. {7,-5,6,-11,-10,10,3,-9,0,15,-1,3,15,3,15,13}

    1727

    32

    Returns: { -10, -9, 0, 3, 3, 3, 6, 7, 10, 15 }

  102. {13,12,12,-11,7,10,6,10,10,-13,4,14,-5,1,-4,11}

    9198

    299

    Returns: { -5, 1, 6, 7, 10, 10, 11, 12, 12, 14 }

  103. {-9,0,-1,3,9,2,9,-2,4,10,7,-1,14,0,-10,14}

    8914

    357

    Returns: { -1, 0, 2, 3, 4, 7, 9, 9, 10, 14, 14 }

  104. {-9,-11,4,-14,-4,2,-10,-5,-11,-6,9,13,6,6,3,13}

    8435

    183

    Returns: { -14, -11, -11, -10, -9, -5, -4, 3, 4, 6 }

  105. {14,0,-9,2,7,-2,0,13,10,2,4,10,7,-11,0,6}

    7988

    151

    Returns: { -11, -9, -2, 0, 0, 2, 2, 4, 7, 7, 10, 13, 14 }

  106. {-14,0,13,9,-2,7,0,-1,14,-5,-12,-9,1,15,1,0}

    2725

    79

    Returns: { -14, -9, -5, -2, -1, 0, 0, 0, 1, 9 }

  107. {8,-5,-13,-8,-2,-6,-8,7,2,10,-13,-3,7,0,-14,-8}

    4264

    112

    Returns: { -13, -13, -8, -8, -8, -6, -5, -3, -2, 0, 10 }

  108. {0,-13,15,5,5,-7,-6,-7,-8,4,-12,-13,14,9,-3,-1}

    9262

    197

    Returns: { -13, -13, -12, -7, -7, -6, -3, 4, 5, 5 }

  109. {8,9,6,12,13,3,4,13,3,-6,6,7,-3,4,14,-3}

    6684

    491

    Returns: { 3, 4, 6, 6, 7, 8, 9, 13, 13, 14 }

  110. { 40, 227, 248, 250, 278, 299, 310, 393, 438, 470, 504, 559, 573, 616, 631, 981 }

    8252

    938

    Returns: { 248, 250 }

  111. { 2, 5, 8, 15, -14, 0, -2, 3, 0, -10, -3, -9, 6, -13, 4, -1 }

    5787

    170

    Returns: { -14, -10, -3, -1, 0, 0, 2, 3, 4, 5 }

  112. { 0, 0, 1, 1 }

    1

    4

    Returns: { 0, 0, 1, 1 }

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: