OBEXPVAL - Editorial

PROBLEM LINK:

Practice

Contest

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.

1 Like

Can someone point out the mistake in my code, please?
Tried in different ways but all the submissions are wrong.

Is it something silly like the output format? tried in all ways.