PROBLEM LINKS
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 = 1⁄n+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 i⁄i+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.