Equal balls#1316

Equal balls (Editorial)

Let's compute the probability of the opposite event $X$ — that the last two balls removed are of different colors. For this to happen, exactly half of the first $n - 2$ n - 2 removed balls must be white, and the other half must be black.

Consider a Bernoulli trial scheme, where the probability of success (e.g., drawing a white ball) is $p = 1/2$ p = 1/2, and the probability of failure is $q = 1 - p = 1/2$ q = 1 - p = 1/2. The probability that exactly $(n - 2) /2$ (n - 2) / 2 of the first $n - 2$ n - 2 removed balls are white is given by the formula:

P (X) = C_{n - 2}^{n /2 - 1} p^{n /2 - 1} q^{n /2 - 1} = \frac{( n - 2 )!}{( ( \frac{n}{2} - 1 ) ! ) ^{2}} (\frac{1}{2})^{n - 2}

P(X) = C_{n-2}^{n/2-1} p^{n/2 - 1} q^{n/2 - 1} = {(n - 2)! \over \left(\left({n \over 2} - 1\right)!\right)^2} \left({1 \over 2}\right) ^ {n - 2}

It remains to compute the value of $P (X)$ for each input $n$ and print $1 - P (X)$ 1 - P(X).

Although $P (X)$ lies within the range $[0, 1]$ , its direct computation may lead to numerical issues. To avoid this, compute its logarithm:

l n P (X) = l n (n - 2)! - 2 \cdot l n (\frac{n}{2} - 1)! - (n - 2) \cdot l n 2

ln P(X) = ln(n - 2)! - 2 \cdot ln\left({n \over 2} - 1 \right)! - (n - 2) \cdot ln~2

After computing the right-hand side of the equation, exponentiate the result to obtain $P (X)$ . The logarithm of a factorial is computed as the sum of logarithms:

l n n! = l n 1 + l n 2 + l n 3 + ... + l n n

ln~n! = ln~1 + ln~2 + ln~3 + ... + ln~n

Since the program processes multiple test cases, all results should be precomputed and stored in an array.

Example

For $n = 6$ n = 6, the probability that the last two balls removed will be of different colors is

C_{4}^{2} p^{2} q^{2} = 6 \cdot (\frac{1}{2})^{4} = \frac{6}{16} = \frac{3}{8}

C_4^2~p^2q^2 = 6 \cdot \left({1 \over 2} \right)^4 = {6 \over 16} = {3 \over 8}

The probability that the last two balls removed will be of the same color is

1- \frac{3}{8} = \frac{5}{8} = 0, 625

1 – {3 \over 8} = {5 \over 8} = 0,625

Algorithm implementation

Declare the necessary arrays. In the cell $an s [i]$ , store the value $C_{i - 2}^{i /2 - 1} p^{i /2 - 1} q^{i /2 - 1}$ C_{i-2}^{i/2-1} p^{i/2 - 1} q^{i/2 - 1}.

#define MAX 100001
double lf[MAX], ans[MAX];

Fill the array $l f$ , where $l f [i]$ stores the value $l ni!$ .

res = lf[1] = 0.0;
for (res = 0, i = 2; i < MAX; i++)
{
  res += log((double)i);
  lf[i] = res;
}

For each value of $i$ , compute $l n C_{i - 2}^{i /2 - 1} p^{i /2 - 1} q^{i /2 - 1}$ ln~C_{i-2}^{i/2-1} p^{i/2 - 1} q^{i/2 - 1} and store the result in $an s [i]$ .

for (i = 2; i < MAX; i += 2)
{
  res = lf[i/2-1];
  res = lf[i-2] - (i - 2) * log(2.0) – res - res;
  ans[i] = exp(res);    
}

For each input value of $n$ , compute and print the result.

while (scanf("%d",&n) == 1)
  printf("%.8lf\n",1 - ans[n]);