Expected Minimum Power#11262

Expected Minimum Power (Editorial)

There are $C_{n}^{x}$ C_n^x ways to choose $x$ distinct integers from $n$ .

Let us consider how many subsets of $x$ numbers have the minimum element equal to $i$ . For this, the subset must include the number $i$ , and additionally choose $x - 1$ x - 1 numbers, each of which is strictly greater than $i$ . There are $n - i$ n - i numbers greater than $i$ , and the number of ways to choose $x - 1$ x - 1 numbers from them is $C_{n - i}^{x - 1}$ C_{n-i}^{x-1}.

Note that the inequality $i + x - 1 \leq n$ i + x - 1 \le n must hold; otherwise, it is impossible to choose $x - 1$ x - 1 numbers greater than $i$ . This leads to the constraint $i \leq n - x + 1$ i \le n - x + 1.

To compute the expected value of the $2^{S}$ 2^S, we need to find the weighted average of this value over all possible subsets:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{\sum _{i = 1}^{n - x + 1} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}}

\frac{\sum_{i = 1}^n 2^i \cdot C_{n - i}^{x - 1}}{C^x_n} = \frac{\sum_{i = 1}^{n - x + 1} 2^i \cdot C_{n - i}^{x - 1}}{C^x_n}

If $i > n - x + 1$ i > n - x + 1, then the number of corresponding subsets is considered to be zero.

Example

In the first test case, there is only one possible selection: ${1, 2, 3, 4}$ \{1, 2, 3, 4\}. The minimum element is $1$ , so the required value is $2^{1} = 2$ 2^1 = 2.

In the second test case, there are three equally likely selections: ${1, 2}$ , ${1, 3}$ and ${2, 3}$ . The corresponding values of $S$ are $1$ , $1$ and $2$ . Therefore, the average value of the $2^{S}$ 2^S is

(2^{1} + 2^{1} + 2^{2}) /3 = 8/3 = 2.6666666

(2^1 + 2^1 + 2^2) / 3 = 8 / 3 = 2.6666666

Now compute the required answer using the formula:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{2 ^{1} \cdot C _{2}^{1} + 2 ^{2} \cdot C _{1}^{1}}{C _{3}^{2}} = \frac{2 \cdot 2 + 4 \cdot 1}{3} = \frac{8}{3}

\frac{\sum_{i = 1}^n 2^i \cdot C_{n - i}^{x - 1}}{C^x_n} = \frac{2^1 \cdot C_2^1 + 2^2 \cdot C_1^1}{C^2_3} = \frac{2 \cdot 2 + 4 \cdot 1}{3} = \frac{8}{3}

Algorithm implementation

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k. The values of the binomial coefficients will be stored in the cells of the array $d p$ .

long long dp[51][51];

long long Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

C++

The main part of the program.

scanf("%d %d", &n, &x);
memset(dp, -1, sizeof(dp));

Compute the answer: $\frac{\sum _{i = 1}^{n - x + 1} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}}$ \frac{\sum_{i = 1}^{n - x + 1} 2^i \cdot C_{n - i}^{x - 1}}{C^x_n}.

a = 0;
for (i = 1; i <= n - x + 1; i++)
   a = a + Cnk(n - i, x - 1) * (1LL << i);
res = 1.0 * a / Cnk(n, x);

Print the answer.

printf("%lf\n", res);