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 |
0) | |
| { 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.
|
|
|
1) | |
| { 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. |
|
|
2) | |
| | Returns: {1.0, 0.0 } | This is a meaningless round.
|
|
|
3) | |
| | 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.
|
|
|
4) | |
| { 1, 1, 1, 2, 2, 2, 3, 3, 3 } | { 4, 5, 6, 4, 5, 6, 4, 5, 6 } | 1 |
| 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 } | |
|
5) | |
| { 1, 2, 5, 4 } | { 9, 7, 8, 9 } | 3 |
| Returns:
{0.6527777777777779, 0.0, 0.34722222222222227, 0.21296296296296297, 0.0, 0.9305555555555559, 0.0, 0.856481481481482 } | |
|
6) | |
| { 3, 317, 25, 447, 96, 333, 361, 103 } | { 947, 773, 601, 544, 594, 399, 786, 954 } | 6 |
| 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 } | |
|