## 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 x_{1}, x_{2}, …, x_{N}, 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**), **F _{X}(x)** := Prob {

**X <= x**} =

**x**

For an expression of the form “max(expr1, expr2)” (i.e. something that looks like **X** = max(**X _{1}, X_{2}**) where

**X**and

_{1}**X**are expressions),

_{2}

F:= Prob {_{X}(x)X <= x}

= Prob {max(**X _{1}, X_{2}**) <=

**x**}

= Prob {**X _{1} <= x**

*and*

**X**}.

_{2}<= xNow, since

Xand_{1}Xconsist of independent random variables, we get that_{2}

Prob {**X _{1} <= x**

*and*

**X**}

_{2}<= x= Prob {**X _{1} <= x**} * Prob {

**X**}

_{2}<= x= **F _{X1}(x) * F_{X2}(x)**

Similarly for an expression of the form “min(expr1, expr2)”. Let **X** = min(**X _{1}, X_{2}**)$. Now,

F= Prob{min(_{X}(x)X) <=_{1}, X_{2}x} = Prob {X_{1}<= xorX}. In terms of sets, this becomes_{2}<= x

Prob( {**X _{1} <= x**} ∪ {

**X**}).

_{2}<= xFinally, 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

**F _{X}(x) = F_{X1}(x) + F_{X2}(x) - F_{X1}(x) * F_{X2}(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 ∫ x^{n} = ^{1}⁄_{n+1} x^{n+1} (ignoring constants of integration etc).

Also, E[X] = ∫_{0}^{1} x f_{X}(x) dx, where f_{X}(x) is the probability density function of X, and is dF_{X}/dx. Thus, if F_{X} = ∑_{i=0}^{k} c_{i} x^{i}, then, xf_{X} = ∑i=1^{k} i c_{i} x^{i}, and hence the integral (with limits from 0 to 1) would be ∑_{i=1}^{k} ^{i}⁄_{i+1} c_{i} x^{i}.

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] = ∫_{0}^{1}(1-F_{X}(x))dx

= 1 - ∫_{0}^{1} F_{X} 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.