Connection Status:
Competition Arena > CandyBox

CandyBox

SRM 462 · 2009-11-12 · by Nickolas

SRM 462 · 2009-11-12 · by Nickolas · Dynamic Programming, Math
Class Name: CandyBox
Return Type: double[]
Method Name: expectedScore
Arg Types: (int, vector<int>, int)
Problem Statement

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.

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, 10}
1
Returns: {10.0, 1.0 }

The swap can be done in only one way.

3)
1
{1, 10}
2
Returns: {1.0, 10.0 }

Two swaps return the box to its original state.

4)
10
{5}
100
Returns: {5.0 }

There is only one kind of candies.

5)
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.

Submissions are judged against all 89 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CandyBox with a public method vector<double> expectedScore(int C, vector<int> score, int S) · 89 test cases · 2 s / 256 MB per case

Submitting as anonymous