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 vector 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 vector 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, vector , int
Returns:vector
Method signature:vector expectedScore(int C, vector score, int S)
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 }
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)2010, TopCoder, Inc. All rights reserved.