LOOPEXP - Loop Expectation
Consider the following pseudo-code
int max = -1;
for i = 1..N:
if(a[i] > max)
max = a[i];
Your task is to calculate the expected number of times the 'if' block of the above pseudo-code executes. The array 'a' is a random permutation of numbers from 1..N chosen uniformly at random.
First line contains t, the number of test cases. t lines follow, each containing N, the number of elements in the array.
1<= t <= 100
1<= n <=100,000
For each test case, output a single decimal. Your answer should be within 10^-6 of the correct answer.
for N=2, you can have the following two permutations: [1,2] and [2,1] .
for the first case the if block gets executed 2 times and for the second one the if block gets executed 1 time. So the expected
value is (3)/2 = 1.5
Found the pattern quickly, spent 1.5h trying to reduce the formula to something computable. Failed, tried what I thought was bruteforce, expected TLE - got AC! Not a good time though so decided to precompute, expected WA due to floats - got AC and best time in Python! Rare case of positive WTF.
Enjoyed deriving the formulae :)
use double instead of float.
Easy. Find the logic.
enjoyed solving it
Anubhav Balodhi :
Once you work on paper, the problem is simpler...
someone please tell the answer for n=6
I found the pattern.. But what does 10^-6 of the correct answer mean ?? I think i am getting WA because of this
Very nice problem.. :)