SemifinalAssignment | Topcoder Archive

Problem Statement

You have advanced to Online Round 5 of the 2010 CodeTopper Open! There are N people competing in this round and the k highest scoring competitors will advance to the Onsite Semifinal Rounds.

The competitors are numbered from 0 to N - 1. In Online Round 5, competitor i will score an integer point value between worst[i] and best[i], inclusive. Every integer point value in this range has the same probability. If two or more competitors get the same score, the lower-numbered competitors are preferred when determining the top k.

After the k advancers are determined, they will be assigned to either Semifinal 1 or Semifinal 2. In order of increasing competitor number, the advancers are assigned to the Semifinal rounds in the following order: 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, ... Note that the scores of the advancers are not considered when determining the Semifinal assignment.

Return a double[] containing 2N elements where the (2i+j)-th (1-based) element is the probability that competitor i is assigned to Semifinal j.

Definition

Class:: SemifinalAssignment
Method:: getProbability
Parameters:: int[], int[], int
Returns:: double[]
Method signature:: double[] getProbability(int[] worst, int[] best, int k)
(be sure your method is public)

Notes

Each element of the returned value must have an absolute or relative error less than 1e-9.
You can assume that scores of the competitors are mutually independent uniform random variables.

Constraints

worst will contain between 1 and 25 elements, inclusive.
worst and best will contain the same number of elements.
Each element of worst and best will be between 0 and 1,000, inclusive.
For each index i, worst[i] will be less than or equal to best[i].
k will be between 1 and the number of elements in worst, inclusive.

Examples

```
{ 1, 0, 1, 1, 1, 1 }
```
```
{ 1, 3, 1, 1, 1, 1 }
```
```
4
```
```
Returns: {1.0, 0.0, 0.0, 0.75, 0.0, 1.0, 0.75, 0.25, 0.25, 0.0, 0.0, 0.0 }
```
There are two possible outcomes of this round: Competitor 1 scores positive points with 75% probability. Then the advancers are competitors 0, 1, 2 and 3. Competitors 0 and 3 are assigned to Semifinal 1, and competitors 1 and 2 are assigned to Semifinal 2. Competitor 1 scores zero points with 25% probability. Then the advancers are competitors 0, 2, 3 and 4. Competitors 0 and 4 are assigned to Semifinal 1, and competitors 2 and 3 are assigned to Semifinal 2.
```
{ 11, 11, 11, 10 }
```
```
{ 12, 12, 12, 11 }
```
```
2
```
```
Returns: {0.875, 0.0, 0.125, 0.625, 0.0, 0.375, 0.0, 0.0 }
```
Competitor 0 will fail to advance only when he/she scores 11 points and each of competitors 1 and 2 scores 12 points.
```
{ 0 }
```
```
{ 1000 }
```
```
1
```
```
Returns: {1.0, 0.0 }
```
This is a meaningless round.
```
{ 1, 2 }
```
```
{ 10, 9 }
```
```
2
```
```
Returns: {1.0, 0.0, 0.0, 1.0 }
```
This is also meaningless because the assignment is based on competitor numbers, not on their scores.

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

{ 4, 5, 6, 4, 5, 6, 4, 5, 6 }

Returns: {0.02041666666666667, 0.0, 0.11527777777777776, 0.0, 0.25810185185185186, 0.0, 0.011435185185185187, 0.0, 0.0875925925925926, 0.0, 0.23171296296296295, 0.0, 0.005046296296296296, 0.0, 0.0625, 0.0, 0.2079166666666667, 0.0 }

{ 1, 2, 5, 4 }

{ 9, 7, 8, 9 }

Returns: {0.6527777777777779, 0.0, 0.34722222222222227, 0.21296296296296297, 0.0, 0.9305555555555559, 0.0, 0.856481481481482 }

{ 3, 317, 25, 447, 96, 333, 361, 103 }

{ 947, 773, 601, 544, 594, 399, 786, 954 }

Returns: {0.6649201903354007, 0.0, 0.32850646461892563, 0.6163949837246063, 0.006573345045673984, 0.4544927900216218, 0.2180181176461977, 0.7769069045939901, 0.3815407626549669, 0.15220532165978432, 0.6601865341758356, 8.501235695949892E-4, 0.7402545855229999, 0.2430210789578823, 0.0, 0.756128797472523 }

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.