MINMAX : Editorial

PROBLEM LINKS

Practice

Contest

Problem Information

Problem Name: Wormtongue’s Mind

Author’s Name: Min-Max Expression

Problem Code: MINMAX

Alphabet: H

Difficulty:

Medium

Pre-requisites:

Probability, Calculus (integration of polynomials)

Problem:

Given an expression consisting of min and max operations over N independent U[0, 1] random variables x1, x2, …, xN, find its expected value.

Solution:

Distributions

It turns out that this problem, though it looks hard, can be solved by figuring out the probability distribution of the expression.

Lets try to find the CDF (Cumulative Distribution Function) of expressions recursively. Note that we consider x ∈ [0, 1] only.

For an expression of the form “x” (i.e. just a uniform random variable X), FX(x) := Prob {X <= x} = x

For an expression of the form “max(expr1, expr2)” (i.e. something that looks like X = max(X1, X2) where X1 and X2 are expressions),

FX(x) := Prob {X <= x}

= Prob {max(X1, X2) <= x}

= Prob {X1 <= x and X2 <= x}.

Now, since X1 and X2 consist of independent random variables, we get that

Prob {X1 <= x and X2 <= x}

= Prob {X1 <= x} * Prob {X2 <= x}

= FX1(x) * FX2(x)

Similarly for an expression of the form “min(expr1, expr2)”. Let X = min(X1, X2)$. Now,

FX(x) = Prob{min(X1, X2) <= x} = Prob {X1 <= x or X2 <= x}. In terms of sets, this becomes

Prob( {X1 <= x} ∪ {X2 <= x}).

Finally, using Prob(A ∪ B) = Prob(A) + Prob(B) - Prob(A ∩ B), along with (as in the case of max) the fact that the random variables are independent, we get

FX(x) = FX1(x) + FX2(x) - FX1(x) * FX2(x).

Thus, we notice that in all cases, the distribution turns out to be some polynomial in x. From here, finding the expected value can be got by integration.

Integration

Recall that ∫ xn = 1n+1 xn+1 (ignoring constants of integration etc).

Also, E[X] = ∫01 x fX(x) dx, where fX(x) is the probability density function of X, and is dFX/dx. Thus, if FX = ∑i=0k ci xi, then, xfX = ∑i=1k i ci xi, and hence the integral (with limits from 0 to 1) would be ∑i=1k ii+1 ci xi.

Alternately, once you have the CDFs, then you can also use E[X] = ∫0 Prob(X>=x) dx, which holds whenever X is a non-negative random variable. In this case, this is

E[X] = ∫01(1-FX(x))dx

= 1 - ∫01 FX dx

Note on Implementation:

You are given the input in the form of a pre-order traversal of the expression tree. It would be good to actually build a tree out of this, and store “cdfs” related to each node (which corresponds to an “expression”)

Also, there is heavy use of Polynomials. Hence, it is also advised to use a Polynomial class imbued with operations of “+”, “-” and “*”. Finally, with the given constraints (N <= |S|/2 where S is the input string length), we get that degree of polynomial is linear in number of random variables, and hence O(N^2) per polynomial multiplication is good enough. Polynomials can be stored using an array of 64-bit integers that store the coefficients.

Finally, due to precision requirements, using a double (even for the final calculation) is not good enough (atleast by this approach of calculating polynomials etc.). Hence it was specified to use long double and long long datatypes. In Java, BigDecimal solution passes.

Editorial Original (unformatted) latex version can be found here

1 Like
//