LOOPEXP - Loop Expectation
Consider the following pseudo-code:
int a[1..N]; 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.
Input
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
Output
For each test case, output a single decimal. Your answer should be within 10-6 of the correct answer.
Example
Input: 1 2 Output: 1.5
Explanation
For N = 2, you can have the following two permutations: [1, 2] and [2, 1].
In the first case the if block gets executed 2 times, and in the second case the if block gets executed 1 time. So the expected value is (2 + 1) / 2 = 1.5
hide comments
nadstratosfer:
2017-09-28 04:49:55
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. |
|
sfialok98:
2017-06-26 16:38:07
Nice problem..
|
|
sonudoo:
2017-02-08 13:40:35
Enjoyed deriving the formulae :) |
|
aditya1997:
2016-08-26 08:51:25
use double instead of float.
|
|
square1001:
2016-08-16 04:49:55
Easy. Find the logic. |
|
Archit Jain:
2014-08-20 17:01:18
enjoyed solving it
|
|
Anubhav Balodhi :
2014-08-13 20:45:49
Once you work on paper, the problem is simpler... |
|
SanchitK:
2014-03-24 15:30:14
someone please tell the answer for n=6 |
|
785227:
2014-03-20 13:42:46
I found the pattern.. But what does 10^-6 of the correct answer mean ?? I think i am getting WA because of this |
|
Phoenix007:
2014-02-01 11:18:25
Very nice problem.. :)
|
Added by: | Aman Gupta |
Date: | 2013-04-20 |
Time limit: | 1s-3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own |