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 } | |
|