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
try this link http://codeforces.com/blog/entry/46419
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.. :)