KALADIN - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Raghav Passi
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa

DIFFICULTY:

medium

PREREQUISITES:

probability, expected value

PROBLEM:

You are given a bag containing n balls, i-th of them having a volume of a_i. The probability of taking a ball is equal to its volume divided by the sum of volumes of all the bags in the bag.

SOLUTION

Suppose you want to draw i-th ball. You randomly keep drawing the balls from the bag one by one till you draw the i-th ball. Find the expected number of turns required to draw i-th ball (for each i from 1 to n).

Expected number of turns required for i-th ball = 1 + expected number of balls drawn before the i-th ball.

Expected number of balls drawn before i-th ball can be found as the sum of the probability of j-th ball being drawn before the i-th ball (for each j \neq i).

Probability of j-th ball being drawn before the i-th will be \frac{a_j}{a_i + a_j}.

This the answer for i-th ball will be 1 + \sum\limits_{j=1, j\neq i}^{n} \frac{a_j}{a_i + a_j}

For a fixed i, this value can be calculated in \mathcal{O}(n) time. So, the overall time complexity of this program will be \mathcal{O}(n^2).

Pseudo Code

for (int i = 1; i <= n; ++i) {
	double r = 1.0;
	for (int j = 1; j <= n; ++j) {
		if (j != i) {
			r += 1.0 * a[j] / (a[i] + a[j]);
		}
	}
	printf("%.6lf%c", (double)r, i == n ? '\n' : ' ');
}

Setters and Tester Solution Codes

Setter’s solution
Tester’s solution

2 Likes
2

Can you please provide some other intuition to arrive at the solution. Some, mathematical steps or reasons.

3

Expanding on my comment on the probability of ball a_i drawn before a_j will be

\frac{a_i}{a_i + a_j}

First, let me explain the kind of intuition behind the formula.

Let us find the probability of ball a_1 being drawn before a_2.

For n = 2.
Then, this probability will be \frac{a_1}{a_1 + a_2}.

For n = 3.

  • At the first draw, draw a_1. Probability a_1 being before a_2 is \frac{a_1}{a_1 + a_2 + a_3}
  • At the first draw, we draw a_3, the probability will be \frac{a_3}{a_1 + a_2 + a_3} \times \frac{a_1}{a_1 + a_2}

The sum of these two expressions is

\frac{1}{a_1 + a_2 + a_3} (a_1 + \frac{a_1 a_3}{a_1 + a_2})

Take a_1 common.

\frac{a_1}{a_1 + a_2 + a_3} (1 + \frac{a_3}{a_1 + a_2})
= \frac{a_1}{a_1 + a_2 + a_3} (\frac{a_1 + a_2 + a_3}{a_1 + a_2})
= \frac{a_1}{a_1 + a_2}

Now, we get an intuition that the expression doesn’t depend on anything other than a_1 and a_2.

Let us prove this by induction.

Suppose this is true for any < n balls. We prove it for n balls.

Let S = a_1 + a_2 + \dots + a_n

  • At the first draw, draw a_1. Probability a_1 being before a_2 is \frac{a_1}{S}
  • At the first draw, we draw a_3, the probability will be \frac{a_3}{S} \times (\text{probability of drawing ball } a_1 \text{before } a_2 \text{ in the remaining } n - 1 \text{ balls, which will be given by } \frac{a_1}{a_1 + a_2} by induction. So, we get
\frac{a_3}{S} \times \frac{a_1}{a_1 + a_2}
  • Similarly, we draw a_4, and probability will be
\frac{a_4}{S} \times \frac{a_1}{a_1 + a_2}
  • …
  • and so on, till we draw a_n, and the probability will be
\frac{a_n}{S} \times \frac{a_1}{a_1 + a_2}

Summing all these expressions together, we get

\frac{a_1}{S} + \frac{a_3}{S} \times \frac{a_1}{a_1 + a_2} + \dots + \frac{a_n}{S} \times \frac{a_1}{a_1 + a_2}
\frac{a_1}{S} + \frac{a_1}{a_1 + a_2} \times (\frac{a_3 + a_4 + \dots + a_n}{S})
\frac{a_1}{S} + \frac{a_1}{a_1 + a_2} \times (\frac{S - a_1 - a_2}{S})

Take \frac{a_1}{S} common.

\frac{a_1}{S} (1 + \frac{S - a_1 - a_2}{a_1 + a_2})
= \frac{a_1}{S} \frac{S}{a_1 + a_2}
= \frac{a_1}{a_1 + a_2}

Hence, proved.

2 Likes
4

Which part is not convincing enough for you?

5

I was unable to understand this part “Probability of j-th ball being drawn before the i-th is a[j] / (a[i]+a[j])”.

6

Any Update ??

7

Hi @samag_1996: I will update tonight. Sorry for the delays :frowning:

8

Try an example of two/three balls, create an expression for it. You will realize the expression. I don’t have a pretty much intuitive explanation for it. Though it is kind of natural that expression should only involve a_i, a_j. For proof, you have to do this via trying smaller examples and generalizing. I don’t have a better one for it :frowning:

9

@samag_1996: I have added an explanation regarding this. Please see my answer below.

10

Can someone explain this part? @admin

11

question

Here first why we add 1 ???