SPOJ LOOPEXP

Link : LOOPEXP

Category : Maths, Expectation

Hint : Consider the smallest element of the array. Consider the two cases of it being the first element of the array and not being the first element of the array.

Code:

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:

Codechef ARIGEOM

Link : ARIGEOM

Category : Pigeonhole principle

Solution : Consider the first three terms. Some two of them have to be in AP or both in GP, thus giving 6 possible cases. Eg, let a,b,and c be first three terms. If a and b form an AP, then common difference of the AP must be b-a. Now mark all elements falling in this AP as apmarked (remember, all elements must be present in this AP starting from a and ending at some end point within the array). Now for remaining elements, find the common ratio that would mark all remaining elements, and possibly some apmarked elements too. Similarly for other 5 cases too.

Code: