# PROBLEM LINK

# DIFFICULTY

EASY

# PREREQUISITES

Simple Math, Dynamic Programming

# PROBLEM

Two types of players are competing in an elimination tournament between 2^{k} players.

Type 1 beats Type 1 by 50
Type 2 beats Type 2 by 50

Type 1 beats Type 2 by P
Type 2 beats Type 1 by (100 - P)

Given the positions of Type 1 players in the tournament draw, find out the probability that the winner is a Type 1 player.

# QUICK EXPLANATION

Let P(i,r) be the probability that player at the i^{th} draw is a Type 1 player in the r^{th} round.

P(i,0) = 1: iff there is a Type 1 player at i^{th}draw initially = 0: otherwise P(i,r) is a function of (P(2*i-1, r-1), P(2*i, r-1))

You can find the expression for P(i,r), and the answer would be P(1,k).

Of course, 2^{k} is too big to test all the values. The crucial insight in this problem, is that several P(i,0) are 0. Infact, only a maximum of 10000 P(i,0) are 1. Also, the number of non-zero P(i,r) values is half the number of non-zero P(i,r-1) values.

Hence, a DP approach from Round 0 to Round k saving only those P(i,r) which are non-zero, will solve the problem.

# EXPLANATION

Let us derive the expression for `P(i,r)`

Let `P(2*i-1, r-1) = p`

, and `P(2*i, r-1) = q`

**Case 1**: Both `2*i-1`

and `2*i`

are Type 1 players

**Probability**: `p*q`

The next player will always be a Type 1 player. Hence this case contributes `p*q`

to `P(i,r)`

**Case 2**: Exactly 1 of `2*i-1`

and `2*i`

are Type 1 players

**Probability**: `p*(1-q) + (1-p)*q`

The Type 1 player will proceed with probability P. The Type 2 player will proceed with probability (1-P). Hence this case contributes `p*(1-q)*P + (1-p)*q*P`

to `P(i,r)`

Hence, `P(i,r) = p*q + p*(1-q)*P + (1-p)*q*P`

We use the above expression to write the following brute force approach.

Given P(i,0) is 1 if i^{th}player is Type 1, and 0 otherwise. total_players = N for round = 1 to k total_players /= 2 for player = 1 to total_players p = P(2*player - 1, round - 1) q = P(2*player, round - 1) P(player, round) = p*q + p*(1-q)*P + (1-p)*q*P return P(1, k)

But, the brute force approach is too slow. It has complexity O(NK).

The insight that helps now is,

**there are several values P(i, 0) that are 0**, and

**if there are M values P(i,r) which are non-zero, then there are at most M values P(i,r+1) which are non-zero.**

Thus, you may store only those values which are non-zero for an algorithm of complexity O(MK) for each test case.

This can be done by iterating through the non-zero P(i, r) values and updating the corresponding P(i/2, r+1) values. Note that you will have to check whether P(i+1, r) (or P(i-1, r)) is also non-zero to update P(i/2, r+1) correctly.

See the tester’s solution for implementation.

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here