TOURNAM - Editorial

editorial
, , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Simple Math, Dynamic Programming

PROBLEM

Two types of players are competing in an elimination tournament between 2k 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 ith draw is a Type 1 player in the rth round.

P(i,0) = 1: iff there is a Type 1 player at ith 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, 2k 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 ith 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

5 Likes
2

Isnt this statement incorrect -

“if there are M values P(i,r) which are non-zero, then there are at most ciel(M/2) values P(i,r+1) which are non-zero.”

since suppose players 2,4,6 have non zero p values at stage r

then in next round (r+1) , players 1,2,3 will have non zero p values

3

Thanks for pointing that out :slight_smile:

I have fixed it.

4

I used the same O(MK) approach in python but it was giving TLE. Submission id 1490994. Was it because python is too slow? Can anyone check please?

5

Code of problem setter is just so clean !!
Awesome

6

P(i,r) be the probability that player at the ith draw is a Type 1 player in the rth round, not able to understand this line at all… can anyone explain…

7

I tried hard but i couldn’t understand the problem setter solutions completely. Can you explain it a bit.

8

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

can anyone explain this part?