TopCoder problem "TournamentWinner" used in TCHS09 Round 2 (Division I Level Two)



Problem Statement

    You are running a local tournament with 8 competitors. The tournament will consist of 3 rounds and will be organized as follows.

In round 1 game i is played between competitors 2*i and 2*i+1 (0<=i<=3). 4 winning competitors advance to round 2.

In round 2 game i is played between the winners of games 2*i and 2*i+1 (0<=i<=1). 2 winning competitors advance to round 3.

Finally, the winners of round 2 games play one game in round 3 to determine the winner of the tournament.

You are given a int[] P describing the percent probabilities of each competitor winning a game against another competitor. The first 7 elements of P are the probabilities of competitor 0 winning a game against competitors 1 through 7, the next 6 elements are the probabilities of competitor 1 winning a game against competitors 2 through 7, etc.

Return a double[] containing exactly 8 elements, where the i-th element is the probability of competitor i winning the tournament.
 

Definition

    
Class:TournamentWinner
Method:winningProbabilities
Parameters:int[]
Returns:double[]
Method signature:double[] winningProbabilities(int[] P)
(be sure your method is public)
    
 

Notes

-The games played in the tournament will not end in a tie.
-Each element of your return must have an absolute or relative error less than 1e-9.
 

Constraints

-P will contain exactly 28 elements.
-Each element of P will be between 0 and 100, inclusive.
 

Examples

0)
    
{5,   0,  10,  15,  20,  25,  30,
      0,  35,  40,  45,  50,  55,
         100, 100, 100, 100, 100,
               60,  65,  70,  75,
                    80,  85,  90,
                         95,  50,
                              50}
Returns: {0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0 }
Competitor 2 wins a game against any other competitor with probability 1.0, so he will win the tournament, leaving no chances to other competitors.
1)
    
{100,  25,   0,  25,  25,  25,  25,
       25,  25,  25,  25,  25,  25,
             0,  25,  25,  25,  25,
                 50,  25,  25,  25,
                     100,  25, 100,
                           25,  25,
                                 0}
Returns: {0.0, 0.0, 0.0, 0.5, 0.5, 0.0, 0.0, 0.0 }
In round 1, players 0, 3, 4 and 7 win against players 1, 2, 5 and 6, respectively. In round 2, 3 wins against 0 and 4 wins against 7. Finally, both 3 and 4 have a 50% chance to win against the opponent in round 3 and to win the tourney.
2)
    
{50,  50,  50,  50,  50,  50,  50,
      50,  50,  50,  50,  50,  50,
           50,  50,  50,  50,  50,
                50,  50,  50,  50,
                     50,  50,  50,
                          50,  50,
                               50}
Returns: {0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125 }
All competitors have equal chances.
3)
    
{100, 50,  50,  50,  50,  50,  50,
       0,  50,  50,  50,  50,  50,
          100,  50,  50,  50,  50,
                 0,  50,  50,  50,
                    100,  50,  50,
                           0,  50,
                              100}
Returns: {0.25, 0.0, 0.25, 0.0, 0.25, 0.0, 0.25, 0.0 }
Competitors 0, 2, 4 and 6 win their games in round 1 and have equal chances in later rounds.
4)
    
{ 50, 50,  50,  50,  50,  50,  50,
      50,  50,  50,  50,  50,  50,
           50,  50,  50,  50,  50,
                50,  50,  50,  50,
                    100, 100, 100,
                          10,  20,
                               30}
Returns: {0.125, 0.125, 0.125, 0.125, 0.5, 0.0, 0.0, 0.0 }
Competitor 4 will get to round 3 for sure, while competitors 0, 1, 2 and 3 have equal chances to get to round 3.
5)
    
{  1,  2,   4,   7,  11,  16,  22,
       3,   5,   8,  12,  17,  23,
            6,   9,  13,  18,  24,
                10,  14,  19,  25,
                     15,  20,  26,
                          21,  27,
                               28}
Returns: 
{6.88919608E-5, 0.009061234459199999, 0.011498979459599998, 0.1853675541204, 0.0328889066112, 0.18542493028680002, 0.17985791390280004, 0.3958315891991999 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9928

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13729&pm=9928

Writer:

Nickolas

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Math, Simulation