Statistics

Problem Statement for "TheKFactor"

Problem Statement

Bob has been selected to compete on a game show called The K Factor. The rules are as follows: The game is played on a strip of N cells that goes from the left to the right. The cells are numbered from 0 to N-1, starting on the left end. Additionally, each cell of the grid has a value written on it. You are given these values in the int[] values. Bob starts the game on cell 0. During the game he will sometimes be asked to make a move. Each time he is asked to do so, he has two options: he can either end the whole game (remaining where he stands at that moment), or move one cell to the right. The amount he wins is the value written in the cell where he stands at the end of the game. Of course, there is a catch. At the beginning of the game, the host of the show generates a secret integer K. The value of K is always between 0 and N-1, inclusive. K is then used as the maximum number of times the host will ask Bob to make a move. (If Bob actually makes K moves to the right without deciding to end the game, after Bob's K-th move the host will terminate the game. In this case Bob still gets the amount written in the cell where he finished the game.)

The host of the show keeps the value of K secret from Bob. However, Bob does have some information about K. He knows that K is chosen at random. He does not know the exact probability distribution used by the host when generating K, but he knows one property of this probability distribution: for each positive integer X, the chance that K is less than X is at most X/N.

Assume that Bob uses the strategy that maximizes the expected value of the amount he wins against the worst possible distribution of values for K. By a "strategy", we mean that Bob selects, for each cell, the probability that he will stop at that cell if he reaches it. Please find the expected value of the amount Bob will win.

Definition

Class:
TheKFactor
Method:
expectedScore
Parameters:
int[]
Returns:
double
Method signature:
double expectedScore(int[] values)
(be sure your method is public)

Notes

  • Your answer will be considered correct if its absolute or relative error does not exceed 10^(-4).

Constraints

  • values will contain between 1 and 50 elements, inclusive.
  • Each element of values will be between 0 and 10000, inclusive.

Examples

  1. {1, 2, 3, 4, 5}

    Returns: 3.0

    Bob should never end this game early. The unique worst-case distribution is {1/5, 1/5, 1/5, 1/5, 1/5}. The expected value of Bob's score is 1 * (1/5) + 2 * (1/5) + 3 * (1/5) + 4 * (1/5) + 5 * (1/5) = 3.

  2. {5, 9, 0, 34}

    Returns: 8.777778

    Bob's optimal strategy can be succinctly described as follows: stop at cell 1 (amount=9) with probability 5/9 and to continue until cell 3 (amount=34) with probability 4/9. One possible worst-case distribution against this strategy is {0, 0, 3/4, 1/4}. Another worst-case distribution is {1/4, 0, 1/2, 1/4}. In both cases, the expected value of Bob's score is 79/9.

  3. {10000, 0, 100}

    Returns: 10000.0

  4. {4374, 5909, 7194, 8367, 1328, 9373, 6067, 7097, 7631, 4841, 2584, 6877, 9775, 2831, 1916, 3253, 8670, 736, 9016, 825, 5002, 8739, 3735, 3262, 5050, 2146, 9273, 5163, 4015, 3174, 1424, 7716, 4162, 9960, 1880, 4320, 7047, 3253, 8702}

    Returns: 8352.585573

  5. {4814, 4710, 5035, 4513, 5046, 4381, 5402, 4372, 6113, 4354, 6205, 4271, 6517, 3989, 6804, 3533, 6811, 3032, 7138, 2848, 7277, 2574, 7278, 2456, 7345, 2239, 7417, 2035, 7519, 1977, 7802, 1920, 8449, 1336, 8612, 1233, 9264, 902, 9284, 690, 9558, 408, 9608, 208, 9661, 139, 9797, 127, 9910, 99}

    Returns: 6077.793513

  6. {0}

    Returns: 0.0

  7. {10000}

    Returns: 10000.0

  8. {107,134,159,851,945,956,1077,1144,1191,1483,1699,1791,2097,2134,2432,2934,3063,3122,3284,3534,3557,3680,3983,4254,4379,4633,5431,5715,5769,5790,5816,5834,6032,6271,6618,6925,7221,7257,7558,8258,8294,8397,8842,8850,9036,9151,9236,9313,9336,9410}

    Returns: 4779.66

  9. {34,150,207,222,236,342,511,752,902,1579,1872,1996,2083,2366,2502,2521,2698,2764,2887,3071,3242,3346,3757,3819,3865,3967,4070,4294,4431,4649,5192,5276,5281,6111,6688,6707,6790,6790,6853,7037,7159,7370,7909,8985,9172,9232,9300,9304,9805,9834}

    Returns: 4398.6

  10. {9928,9353,9246,9037,8580,8561,8549,8392,8321,8215,8148,7738,7682,7599,7451,7426,7023,6730,6584,6348,5960,5741,5732,5493,5491,5461,5418,5373,5250,4998,4792,4381,4317,3993,3828,3400,3325,3066,2962,2712,2679,2329,2005,1875,1680,770,529,406,317,208}

    Returns: 9928.0

  11. {9678,9548,9318,9127,9111,8883,8802,8710,8296,8101,8100,8011,7888,7377,7289,7035,6959,6802,6686,6644,6545,6260,6135,6073,5980,5578,5467,5456,5416,5271,5079,4731,4686,4678,3525,3523,3460,3432,2670,2455,2446,2388,2177,1499,1073,1047,843,598,126,109}

    Returns: 9678.0

  12. {9188,2283,2550,2982,9505,6017,3788,609,8623,6472,3909,7416,7777,9813,4237,9692,9450,1136,892,7919}

    Returns: 9188.0

  13. {6559,3837}

    Returns: 6559.0

  14. {4779,613,2271,6181,2192,8701,1591,6235,5948}

    Returns: 4779.0

  15. {2776,8835,1266,8566,4337,2584,3188,4489,4532,5817,1791,3819,3799,1721,6091,4832}

    Returns: 8456.3125

  16. {3761,5845,7730,7358,4293,2505,7304,3144,8142,9693,695,7661,8377,5668,4464,6786,9771,9798,2782,896,9553,8207,4422,9308,2464,2122,3012,7304,762,2576,9372,5348,9368,1158,3771,3629,6648,1823,5889,5914,9108,9936,6432,6108}

    Returns: 8379.886364

  17. {111,5219,931,9298,1973,5098,3185,6764,5449,3565,4876,9373,1081}

    Returns: 7304.076923

  18. {1883,1069,8957,1975,9839,1850,7061,1883,6915,2917,2565,8708,437,9116,2218,5105,8125,5773,915,3387,4373,5028}

    Returns: 8326.818182

  19. {8145,5599,5022,3834,3530,5038,6769,5120}

    Returns: 8145.0

  20. {4374,5909,7194,8367,1328,9373,6067,7097,7631,4841,2584,6877,9775,2831,1916,3253,8670,736,9016,825,5002,8739,3735,3262,5050,2146,9273,5163,4015,3174,1424,7716,4162,9960,1880,4320,7047,3253,8702}

    Returns: 8352.585573

  21. {9619,6781,6557,4609}

    Returns: 9619.0

  22. {5553,5170,5750,4861,5844,4649,5903,4489,5996,4397,6244,4365,6560,3608,7023,3542,7056,3152,7160,3093,7307,2792,8239,2749,8658,2566,8708,2425,8787,2402,8832,2379,8857,1792,9172,1586,9179,1092,9184,1003,9234,679,9347,492,9432,395,9808,235,9950,224}

    Returns: 6207.808978

  23. {5231,4164,5515,4134,5834,3909,5918,3737,5942,3420,6106,3034,6392,2469,6404,2372,6741,1972,6927,1860,6963,1704,6975,1691,6997,1685,7564,1514,7647,1348,8026,1341,8050,633,8166,518,8190,475,8233,321,8604,274,9320,187,9332,128,9416,75,9544,45}

    Returns: 5721.029689

  24. {5598,4561,5870,4343,6020,3726,6236,3133,6283,3129,6383,3095,6677,3026,6731,2697,6890,2558,6931,2289,7212,2251,7348,2205,7444,2062,7566,1729,7656,1665,7780,1267,8491,1111,8584,988,8658,934,8841,929,9462,909,9551,749,9761,703,9825,683,9887,616}

    Returns: 5957.715606

  25. {4814,4710,5035,4513,5046,4381,5402,4372,6113,4354,6205,4271,6517,3989,6804,3533,6811,3032,7138,2848,7277,2574,7278,2456,7345,2239,7417,2035,7519,1977,7802,1920,8449,1336,8612,1233,9264,902,9284,690,9558,408,9608,208,9661,139,9797,127,9910,99}

    Returns: 6077.793513

  26. {5250,5226,5253,5149,5283,5080,5342,4775,5701,4678,5838,4667,6181,4341,6185,4014,6432,3998,6629,3922,6702,3445,6953,3268,7104,3267,7558,3076,7722,3068,7817,2662,7960,2659,8070,2629,8119,2071,8815,1886,8845,1722,9048,1396,9559,585,9625,540,9848,496}

    Returns: 5836.101927

  27. {5234,5164,5280,5046,5284,4352,5723,4254,5940,4226,6110,4221,6118,4160,6288,3853,6328,3766,7328,3474,7340,3405,7499,3397,7539,3387,7608,3139,7614,2849,7654,1826,7870,1791,7875,1559,8168,1348,8506,1280,8950,1241,9103,1222,9359,1027,9613,851,9932,281}

    Returns: 6085.714208

  28. {5463,4329,5507,4090,5937,4025,5946,3811,6129,3681,6209,3292,6374,3176,6973,2914,7225,2733,7246,2548,7284,2378,7396,2270,7419,2093,7450,1730,7489,1718,8171,1678,8340,1475,8420,1286,8466,998,8683,935,8952,711,9416,687,9499,616,9636,349,9998,178}

    Returns: 5979.729141

  29. {5456,5400,5630,5191,5642,4834,5718,4649,5725,4375,5836,4276,6345,4246,6490,3974,6505,3948,6605,3896,6636,3362,6699,3339,6761,2388,7132,2384,7368,2338,7377,2281,7626,1895,7982,1796,8623,1639,8624,1551,8646,1542,9104,1537,9198,1226,9586,1115,9703,221}

    Returns: 5868.587861

  30. {3989,3611,4516,3525,4826,3501,4967,3390,5081,3288,5518,2847,5678,2565,5818,2420,5870,2239,5963,2234,6113,1897,6118,1857,6193,1606,6249,1491,6868,1479,7515,887,7608,816,7793,726,8687,607,8730,589,8833,474,8889,438,9078,423,9339,145,9832,50}

    Returns: 5084.323025

  31. {6733,6591,6866,6422,6966,6010,7006,5449,7244,5219,7437,5019,7487,4907,7527,4625,7594,4558,7646,4499,7677,4495,7713,4269,7742,3720,8102,3661,8190,3605,8520,3340,8623,2409,8713,1847,8885,708,9075,559,9136,448,9447,316,9604,98,9725,72,9737,20}

    Returns: 7021.86321

  32. {1000,1100,979,1107,958,1116,930,1127,898,1141,872,1158,826,1180,823,1204,794,1233,787,1266,777,1304,740,1351,712,1408,693,1476,658,1560,611,1667,605,1799,604,1967,596,2188,585,2491,546,2938,526,3646,484,4936,471,7950,467,10000}

    Returns: 1128.245102

  33. {1000,1100,968,1108,944,1117,900,1129,876,1144,873,1161,850,1181,800,1206,786,1235,744,1271,731,1313,718,1362,669,1423,641,1497,607,1589,598,1701,580,1840,575,2016,525,2255,519,2582,495,3059,447,3823,409,5213,387,8471,376,10000}

    Returns: 1126.936989

  34. {1000,1100,956,1108,938,1118,920,1129,890,1143,861,1160,850,1180,815,1204,771,1234,746,1269,745,1309,725,1357,697,1415,649,1487,616,1576,598,1686,581,1824,556,2002,518,2240,513,2566,505,3039,461,3794,452,5157,402,8371,392,10000}

    Returns: 1126.423131

  35. {1000,1100,997,1106,981,1113,933,1124,911,1137,862,1155,852,1175,841,1198,814,1225,804,1257,774,1295,759,1340,756,1392,732,1454,720,1529,678,1625,637,1748,623,1906,594,2117,586,2407,547,2834,499,3519,477,4759,444,7674,405,10000}

    Returns: 1126.112481

  36. {1000,1100,983,1107,966,1115,948,1125,939,1136,906,1151,894,1168,893,1187,889,1208,858,1234,834,1265,792,1304,770,1352,768,1408,749,1476,741,1559,697,1667,674,1807,665,1992,618,2253,594,2635,573,3241,555,4339,534,6914,523,10000}

    Returns: 1127.433376

  37. {1000,1100,957,1108,911,1119,894,1132,864,1148,830,1167,784,1191,748,1220,715,1255,707,1294,664,1342,648,1398,638,1464,614,1543,609,1638,570,1757,563,1905,514,2099,510,2353,471,2707,463,3220,453,4029,448,5486,428,8900,407,10000}

    Returns: 1126.315231

  38. {1000,1100,998,1106,976,1114,939,1125,896,1139,867,1156,827,1178,796,1204,787,1233,748,1269,720,1312,681,1365,677,1427,668,1499,626,1589,599,1701,583,1841,540,2024,508,2269,501,2604,455,3098,427,3883,390,5306,364,8641,316,10000}

    Returns: 1127.106732

  39. {1000,1100,974,1107,936,1117,907,1129,893,1143,884,1159,849,1179,836,1202,830,1228,806,1259,759,1297,730,1343,722,1397,721,1461,691,1540,678,1637,668,1757,659,1910,631,2115,609,2399,586,2814,578,3468,573,4647,548,7415,547,10000}

    Returns: 1126.432497

  40. {1000,1100,980,1107,936,1117,896,1130,888,1145,855,1163,814,1186,773,1213,772,1243,726,1280,682,1326,652,1381,626,1447,594,1527,578,1624,556,1744,544,1892,539,2081,509,2332,474,2681,471,3186,429,3992,398,5455,355,8897,350,10000}

    Returns: 1126.673612

  41. {1000,1100,955,1108,932,1118,900,1130,879,1145,876,1161,853,1181,826,1205,817,1232,772,1265,730,1306,728,1353,686,1411,650,1483,603,1573,553,1688,544,1830,507,2015,457,2264,443,2607,433,3104,421,3888,403,5307,367,8642,322,10000}

    Returns: 1126.73986

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: