Problem link: http://www.codechef.com/download/ACMAMRITA12/H_Min_Max_expression.pdf
I cannot get any idea to solve this problem? I only proved that the expected value of min(x,y) = 1/3 and max(x,y) = 2/3 when x and y in the range [0,1] using double integrals. However, I cannot get any idea to solve the rest of the problem when many min-max branches are involved. Thanks in advance.
I will give you a hint:
For every node, calculate a polynomial p(x), which gives the probability of the value of node being < x.
You can calculate this if you know the probability polynomial for its children.
Actually I got the polynomial of min and max:
prob of min(x,y) = ( x^2 + y^2 ) / 2 - ( x^3 + y^3 ) / 3
prob of max(x,y) = ( x^3 + y^3 ) / 3
But after trying to generalize when getting results from children, I get wrong answer for the third test case
Can you please elaborate your solution more?