TopCoder Statistics - Problem Statement

Problem Statement

Bob is playing a game. The game is played with a collection of blocks and a single custom-made die.

Each of the blocks has a positive integer written on it. You are given a int[] block. Each element of block is the number written on one of the blocks.

Each of the faces of the die also has a positive integer written on it. You are given a int[] face. Each element of face is the number written on one of the faces of the die. Whenever Bob rolls the die, one of its faces is selected uniformly at random, and Bob uses the number written on that face.

The game is played in turns. Each turn looks as follows:

Bob rolls the die to select a random number R.
Bob selects a subset of blocks such that the sum of their numbers is exactly R.
Bob removes the selected blocks from the game.

In step 2, if there is no such subset, the whole game ends. If there are multiple subsets with the required sum, Bob gets to choose which subset is removed. Note that Bob is not allowed to skip a turn: whenever there is at least one valid subset of blocks, he must choose and remove one such subset.

Bob's score at the end of the game is the sum of the numbers on the remaining blocks. Bob plays the game optimally. More precisely, Bob plays the game in a way that minimizes his expected score at the end of the game. Compute and return the expected value of Bob's score at the end of the game.

Definition

Class:: SubsetSumExtreme
Method:: getExpectation
Parameters:: int[], int[]
Returns:: double
Method signature:: double getExpectation(int[] block, int[] face)
(be sure your method is public)

Notes

Your answer will be accepted if it has absolute or relative error at most 1e-6.

Constraints

block,face will have between 1 and 12 elements, inclusive.
Each element of block,face will be between 1 and 1,000, inclusive.

Examples

{1,2,3}

{6,5}

Returns: 0.5

Bob has three blocks with the numbers 1, 2, and 3. Bob has a two-sided die with the numbers 6 and 5 on its faces. (I.e., Bob has a fair coin that has 6 on one side and 5 on the other side.) Let's look at the first turn of the game. In step 1 Bob will randomly choose either 6 or 5, each with probability 1/2. If he chose 6, he will then select all three blocks. If he chose 5, he will select the block with a 2 and the block with a 3. Finally, he will remove the selected blocks from the game. In either case, the game will end in the second turn. Hence, with probability 1/2 Bob's final score will be 1 and with probability 1/2 his final score will be 0. This means that the expected value of his score is (1/2)*1 + (1/2)*0 = 1/2.
{1,2,1}

{1,2}

Returns: 0.5

Note that Bob's choices matter. For example, assume that in this game he rolls a 2 in the first turn. Now he has two different options: either he removes the two blocks with 1s, or the single block with a 2. One of these two options is strictly better than the other.
{10,11,12}

{3,4,5,6}

Returns: 33.0

The numbers on Bob's blocks are too large. This game will end already in its first turn, and Bob's score is guaranteed to be 33.
{1,1,1,1}

{1}

Returns: 0.0

This game will end on turn 5. In each of the previous four turns Bob rolls a 1 and removes one of the four blocks from the game.
{3,2,2,3}

{2,3,2,3,2,3}

Returns: 2.1875
{968,423,592,419,321,253,62,42,12,32,2,4}

{968,423,592,419,321,253,62,42,12,32,2,4}

Returns: 1996.9320680897076
{12,11,10,9,8,7,6,5,4,3,2,1}

{12,12,12,12,12,6,6,6,3,3,2,1}

Returns: 40.03765576104895
{448,7,14,254,103,5,420,147,2,1,11,123}

{96,443,203,247,460,524,134,274}

Returns: 1163.416015625
{1,2,3,4,5,6,7,8,9}

{2,2,2,2,3,3,4,4,1,5,10,30}

Returns: 27.982703189300413
{871,582,651,519,713,664,859,212,530,671}

{868,712,279,447}

Returns: 6272.0
{278,79,758,642,121,839,266}

{671,210,408,840,855}

Returns: 2983.0
{105,15,477,538}

{597,430,376,25,6,570,181}

Returns: 1049.7142857142856
{14,276,10}

{568,804,668,295,511,274,738,542,380,617,712}

Returns: 300.0
{34,122,52,87,51,158,190,154}

{37,154,187,131,63,147,82,139,33,102}

Returns: 815.77
{195,1,62,1,9,54,1,35,9,21,313,195}

{4,13,1,7,8}

Returns: 895.752
{12,3,126,94,135,1,3,2,1,11,1}

{68,8,7,173,11,26,1,2,71,88}

Returns: 380.56109999999995
{88,152,93,183,215,252}

{33,105,198,241,200,53,166,136}

Returns: 983.0
{480,373,34,81,521,674,340,398}

{360,324}

Returns: 2901.0
{757,609}

{11,5,520}

Returns: 1366.0
{5,5,1,7,210,6,1,3}

{563,45,653,822,965,330,514}

Returns: 238.0
{40,2,7,12,7,1,3,18,5,1}

{11,7,41,32,36,42,18,10,19,14}

Returns: 36.89516
{12,133,3,35,91,28,22,80,33,102,24}

{117,137,42,42,49}

Returns: 479.32
{383,132,216,324,256,241,589,188,404}

{73,703,720,357,647,462,604}

Returns: 2546.2857142857147
{1,75}

{59,472,315,43}

Returns: 76.0
{583,25,621,47,180,454,550,183,456,361}

{278,425,85,297}

Returns: 3460.0
{2,2,13,6,53,34,347,941}

{2,3,12,36,2,19,48,2}

Returns: 1385.396484375
{393,247,77,214,72,204,76,299}

{381,131,94,252,139,236,350}

Returns: 1582.0
{407}

{182,159,369}

Returns: 407.0
{528,172,83,18,219,392,542,35,547,481}

{543}

Returns: 3017.0
{90,41,358,107,48,393,234,101,97,419}

{375,74,75,263,406,117,215,27}

Returns: 1837.25
{898,11}

{776,689,54,602}

Returns: 909.0
{138,591,76,215,104}

{38,59,707,563,339,443,21,183,730,526,719}

Returns: 1124.0000000000002
{15,1,2,15,55,5,74,4}

{84,78,24,34,27,53,59,34,45,46}

Returns: 136.22
{1,21,12,32,1,632,83,44}

{111,541}

Returns: 770.5
{19,1,675,312,118,26}

{799,339,840,889,823,809,828,137}

Returns: 1084.0625
{549,226,895,388,826,462,142,456,793,89,34}

{18,2,2,533,226,887,1,14,1,963}

Returns: 4837.4
{115,77,45,167,169,77,2,83,66}

{1,154,13,1,2,1,14}

Returns: 775.530612244898
{132,1,20,211,9,12,1}

{67,174,54,296,316,253,82}

Returns: 325.00000000000006
{7,4,71,201,1,1}

{3,5,117,1,143,2}

Returns: 283.47222222222223
{312,158,40,74}

{80,119,2}

Returns: 584.0
{1,186,3,7,17,15,20,2,3,5}

{34,30,1,7,1,1,43}

Returns: 224.8117451062058
{2,80,25,3}

{286,162,217,201}

Returns: 110.0
{528,4,2,70,1,57,7,179,549,5}

{20,36,233,19,3}

Returns: 1397.6
{21,24,537,266,562,492,536,312,145,639}

{334,33,376,542,3,5,12}

Returns: 3533.9999999999995
{39}

{113,215}

Returns: 39.0
{317,636,71,811,840,707,268,263,706}

{280,432,77,301,286}

Returns: 4619.0
{517,253,511,105,458,328,413,149,131,810,631,76}

{4,19,80,184,193,16,476,1,2,549,3}

Returns: 4382.000000000001
{57,128,17,151}

{224,62,169,66,223,176,54}

Returns: 353.00000000000006
{790,971,231,676,765,408,842,898,611,532,535}

{4,290,110}

Returns: 7259.0
{114}

{2,231,68,14,75,11,29}

Returns: 113.99999999999997
{415,33,160,1,429,621,686,647}

{968,224,2,23,20,49,27,530,26}

Returns: 2991.9999999999995
{432,112,322,756,423,458,936,502,517}

{945,540,307,294}

Returns: 4458.0
{114,164,339,60,679,221,908,571}

{848,904,300,450,501,186,396,988,140,677,109}

Returns: 2994.454545454546
{130,962,616,257,717,176,148,803,560,923,789,789}

{874,331,174,727,798,626,557,312,621,677,290,389}

Returns: 6870.0
{98,700,841,654,902,994,70,843,890,265,762,831}

{8,172,3,2,354,82,71,2,275,5,66,10}

Returns: 7850.000000000001
{131,961,742,359,786,801,454,145,654,89,616,851}

{791,931,483,566,874,139,254,557,472,102,423,789}

Returns: 6426.04861111111
{884,636,40,707,800,536,233,903,473,306,971,709}

{937,439,666,678,574,385,883,634,93,226,560,370}

Returns: 7197.999999999999
{230,341,51,145,1,2,40,69,392,257,145,12}

{704,16,955,917,418,744,980,574,64,635,272,820}

Returns: 1065.3472222222222
{2,1,2,5,4,5,6}

{1,3,3,1,1,2,1,4}

Returns: 21.6064453125
{1,1,1}

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

Returns: 0.0
{2}

{4,7,1,1,1,6,2,2,7,7,2,2}

Returns: 1.3333333333333333
{1,1,1,6,1,2,1,2,7,1,2,6}

{9,10,3,4,10,10,10}

Returns: 6.584339858392338
{5,6,1,2,6,4}

{1,3,1,4,6,6,5,4,6,4,1}

Returns: 13.421580741504245
{2,2,1,1,1,1,1,7,8,1,8,2}

{2,3,5,10,4,8,6,4}

Returns: 16.801187455654144
{1,7,3,3}

{6,5,4,6,7}

Returns: 7.640000000000001
{5,1,9,3,2,4,2,8}

{5,4,3,10,5,7,2}

Returns: 15.207940568980613
{6,1,1,6,1,1}

{3,5,2,1,2,2,3,6,1}

Returns: 11.472588678705632
{2,7,4,5,4,1,6}

{9,8,6,9,6,8,5,3,3,4}

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

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

Returns: 11.621065007332259
{6,1,4,6,1,4,1}

{1,8,7,7,1,7,8,3,4}

Returns: 9.177479720232348
{5,1,1}

{6,5,3,1,1,3,3,3}

Returns: 4.8515625
{1,1}

{1,1,1,1,1}

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

{5,6,1,3,5}

Returns: 2.0096
{1,1}

{1}

Returns: 0.0
{1,4,4,5}

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

Returns: 10.215363511659806
{1,1,1,1,1,1,1,1,1}

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

Returns: 0.0
{1,1}

{1}

Returns: 0.0
{2,2,1,1,1,1,1,1,1,1}

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

Returns: 0.40946566614054025
{7,2,2,5,2,4,7,7,4,7,1,5}

{5,3,1,7,7,1,2,7,6,7,5,6}

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

{3,2,1,2,4,2,1,4,2,4,4,3}

Returns: 3.2988856006593394
{9,3,1,5,2,7,6,2,10,2,7,9}

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

Returns: 42.902317293059845
{1,1,2,1,2,2,1,1,2,1,2,2}

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

Returns: 5.480228284983657
{3,1,1,2,1,2,1,2,1,2,1,1}

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

Returns: 4.145274238628092
{10, 11, 12 }

{3, 4, 5, 6 }

Returns: 33.0
{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

{12, 12, 12, 12, 12, 6, 6, 6, 3, 3, 2, 1 }

Returns: 40.03765576104895
{1, 2, 1 }

{1, 2 }

Returns: 0.5
{500, 500, 500, 950, 400, 500, 1000, 1000, 500, 1000, 300, 1000 }

{1000, 1000, 1000, 800 }

Returns: 3325.5615234375

Statistics

Problem Statement for "SubsetSumExtreme"

Problem Statement

Definition

Notes

Constraints

Examples