Skip to content

Winners of a Tournament

Level: L3-L4 Topics: Simulation, Probability, Dynamic Programming, Recursion

Problem Statement

A knockout (single-elimination) tournament has N players, where N is a power of 2. Players are arranged in a bracket and play pairwise matches. The loser of each match is eliminated, and the winner advances. After log2(N) rounds, one player remains as the champion.

You are given a probability matrix P where P[i][j] is the probability that player i beats player j in a head-to-head match.

Solve two variants:

  • (Easy) Deterministic: All probabilities are 0 or 1 (the outcome of every match is known in advance). Simulate the tournament and return the winner.
  • (Medium) Probabilistic: Probabilities are real numbers between 0 and 1. Compute the probability that each player wins the tournament. Return the player with the highest probability of winning.

Background & Constraints

  • N is a power of 2 (e.g., 2, 4, 8, 16).
  • P[i][j] + P[j][i] = 1 for all i != j.
  • P[i][i] is undefined (a player does not play against themselves).
  • Players are indexed 0 to N-1 and placed in bracket order: player 0 vs player 1, player 2 vs player 3, etc. in round 1.
  • For the probabilistic variant, matches are independent.

Examples

Deterministic (N=4):

Players: [0, 1, 2, 3]
P[0][1] = 1  (player 0 beats player 1)
P[2][3] = 0  (player 3 beats player 2)
P[0][3] = 1  (player 0 beats player 3)

Round 1: 0 beats 1, 3 beats 2. Round 2 (Final): 0 beats 3. Winner: Player 0

Probabilistic (N=4):

P[0][1] = 0.8, P[2][3] = 0.6
P[0][2] = 0.3, P[0][3] = 0.5
P[1][2] = 0.4, P[1][3] = 0.7

The probability that player 0 wins the tournament depends on whom they face in the final:

  • P(0 wins) = P(0 beats 1) * [P(2 beats 3) * P(0 beats 2) + P(3 beats 2) * P(0 beats 3)]
  • P(0 wins) = 0.8 * [0.6 * 0.3 + 0.4 * 0.5] = 0.8 * [0.18 + 0.20] = 0.8 * 0.38 = 0.304

Compute similarly for all players and return the one with the highest win probability.

Hints & Common Pitfalls

  • Deterministic case: Simply simulate round by round. Each round halves the number of players.
  • Probabilistic case: Use dynamic programming. Let dp[round][player] be the probability that this player is still alive at the start of the given round. In each round, a player advances only if they beat whoever they face, weighted by the probability that each possible opponent made it to that round.
  • The bracket structure determines who can face whom in each round. In round r, a player in position i can only face someone from the same "group" of size 2^r.
  • A common pitfall is incorrectly computing which opponents a player might face in later rounds. Be precise about the bracket groupings.

Follow-Up Questions

  1. Complexity analysis: What is the time complexity of the probabilistic simulation? (Hint: with N players and log2(N) rounds, processing each round involves checking potential opponents within each bracket group.)