SPOJ AMR12H

Link : AMR12H

Category : Maths, probability and expectation

Solution : If f(x) is the Random Distribution Function of a random variable X and g(x) is the RDF of RV Y then
RDF of min(X,Y) is f(x)*g(x)
RDF of max(X,Y) is f(x)+g(x)-f(x)*g(x)
Then the expected value of the expression formed is integral over [0,1]

Code:

UVA 12356 : Army Buddies

Link : UVA12356

Category : Data Structure

Solution : Simple segment tree data structure suffices. Each node of the tree has a boolean variable indicating if at all it is possible to find an alive soldier in this range of soldiers.

Code: