PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Misha Chorniy
Editorialist: Animesh Fatehpuria
PROBLEM
You are given an array X of at most 10^5 integers and an integer E. Compute any probability distribution
P over X such that the expected value equals E i.e. \sum_{i = 1}^{n} P_i X_i = E. If no solution exists,
print -1.
EXPLANATION
At first glance, the task might seem daunting since we’ve to compute a distribution over reals. The problem doesn’t
have any sort of discrete structure to play with. For problems like this, it is sometimes a good idea to think about
the cases that have no solution in order to give us more insight.
WLOG, assume that the array X is sorted. It is easy to see that we have no solution when E < X_1 or when E > X_n. Intuitively, it should make sense that no distribution can give us an expected value greater than the largest
number or smaller than the lowest number. Additionally, notice that the cases E = X_1 and E = X_n have solutions, since we can simply set P_1 = 1 or P_n = 1 respectively and set the remaining P values to 0.
One might now conjecture that we have a solution iff X_1 \le E \le X_n. It turns out that this is true, since we can come up with a clean constructive scheme to obtain a solution. We first apply a trick which makes the problem
easier for us. We assume that P_2, P_3, \cdots P_{n - 1} are all 0. Now assume that P_1 = p where p \in [0, 1]. Then we know that P_n = 1 - p. The expected value here is P_1X_1 + P_nX_n = pX_1 + (1 - p)X_n. We want this value to equal E. Thus, we can solve for p to get p = \frac{X_n - E}{X_n - X_1}.
So, have we solved the problem? Well, almost! Note that we haven’t shown yet that p \in [0, 1], which is necessary for P to be a probability distribution. But this is quite easy to show. We know that X_1 \le E \le X_n, thus the
numerator of the expression for p is not greater than the denominator. Thus p \in [0, 1].
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.