Google L3 loop R1

Problem statement You have 2^n players in a fixed single elimination tournament, labeled 0 to 2^n - 1. Round 1 is 0 vs 1, 2 vs 3, and so on. In later rounds, winners from neighboring bracket blocks play each other. Given p[i][j], the probability player i beats player j, return the probability each player wins the whole tournament. Solution Simple DP. Maintain: dp[round][player] = probability player survives/wins up to this round Transition: new_dp[x] = dp[x] * sum(dp[y] * p[x][y])