TopCoder problem "CandyBox" used in SRM 462 (Division I Level Two)



Problem Statement

    You have a box containing N kinds of candy. There are exactly C pieces of each kind. Every piece of candy looks the same, but each kind tastes different, so each kind is placed in a separate section of the box. You have assigned a score to each kind of candy indicating how much you like it. The i-th element of the int[] score is your score for the i-th kind of candy.



Your friend's idea of a practical joke is to mix up all the candies in the box, so that each time you choose a candy, you get a surprise. He sneaks into the box and starts swapping random pairs of candies. For each swap, he chooses two distinct candies (independently from previously chosen pairs) and swaps them. All pairs of candies have the same probability of being chosen, and the two candies are not necessarily chosen from different sections of the box. Fortunately, you catch him after he has done only S swaps. Now you want to know how much on average you'll like a piece of candy chosen at random from each section of the box. Return a double[] containing exactly N elements, where the i-th element is the expected score of one candy chosen randomly from the section of the box that originally contained only candies of the i-th kind.
 

Definition

    
Class:CandyBox
Method:expectedScore
Parameters:int, int[], int
Returns:double[]
Method signature:double[] expectedScore(int C, int[] score, int S)
(be sure your method is public)
    
 

Notes

-Each element of the return must have an absolute or relative error less than 1e-9.
 

Constraints

-C will be between 1 and 100, inclusive.
-score will contain between 1 and 50 elements, inclusive.
-Each element of score will be between 1 and 100, inclusive.
-S will be between 0 and 10000, inclusive.
-The total number of candies C*(number of elements in score) will be strictly greater than 1.
 

Examples

0)
    
10
{1, 10}
0
Returns: {1.0, 10.0 }
No swaps were done, so all candies stay in their original sections.
1)
    
2
{1, 10}
1
Returns: {4.0, 7.000000000000001 }
Six pairs of candies can be chosen for the swap. Two of the swaps swap candies of the same type, and all the candies stay in their original sections, and the expected scores of sections are {1, 10}. Four of the swaps swap candies of different types, so in each section there is one candy of each kind, and the expected scores are {5.5, 5.5}. The answer is 1/3 * {1, 10} + 2/3 * {5.5, 5.5} = {4, 7}.
2)
    
1
{1, 4, 10}
1
Returns: {5.0, 5.0, 5.0 }
The swap can turn this box into one of the following: {1, 10, 4}, {4, 1, 10} or {10, 4, 1}. For each section, the probability of finding a candy of a certain kind is 1/3.
3)
    
98
{13, 82, 74, 78, 12, 71, 81, 80, 30}
154
Returns: 
{26.25622829378155, 74.87969915903301, 69.24219529059805, 72.06094722481552, 25.551540310227182, 67.12813133993495, 74.17501117547864, 73.47032319192427, 38.23592401420582 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10744

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14147&pm=10744

Writer:

Nickolas

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Dynamic Programming, Math