TournamentWinner | Topcoder Archive

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

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

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

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

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

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

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

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.