KALADIN - Editorial



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




probability, expected value


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.


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


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

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.


Which part is not convincing enough for you?

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])”.

Any Update ??

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

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:

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

Can someone explain this part? @admin


Here first why we add 1 ???