Connection Status:
Competition Arena > SemifinalAssignment

SemifinalAssignment

TCO10 Semi 1 · 2010-04-11 · by lyrically

TCO10 Semi 1 · 2010-04-11 · by lyrically · Dynamic Programming
Class Name: SemifinalAssignment
Return Type: double[]
Method Name: getProbability
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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)
{ 0 }
{ 1000 }
1
Returns: {1.0, 0.0 }

This is a meaningless round.

3)
{ 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.

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 }

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

Coding Area

Language: C++17 · define a public class SemifinalAssignment with a public method vector<double> getProbability(vector<int> worst, vector<int> best, int k) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous