Having a lot of trouble with this question in interviewstreet.com:
Given array of integers Y=y1,...,yn, we have n line segments such that endpoints of segment i are (i, 0) and (i, yi). Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, v1, ..., vn, where vi is equal to length of ray shot from the top of segment i. We define V(y1, ..., yn) = v1 + ... + vn. For example, if we have Y=[3,2,5,3,3,4,1,2], then v1, ..., v8 = [1,1,3,1,1,3,1,2], as shown in the picture below:
For each permutation p of [1,...,n], we can calculate V(yp1, ..., ypn). If we choose a uniformly random permutation p of [1,...,n], what is the expected value of V(yp1, ..., ypn)?
Input Format First line of input contains a single integer T (1 <= T <= 100). T test cases follow. First line of each test-case is a single integer N (1 <= N <= 50). Next line contains positive integer numbers y1, ..., yN separated by a single space (0 < yi <= 1000). Output Format For each test-case output expected value of V(yp1, ..., ypn), rounded to two digits after the decimal point.
I serious don't want any code or a pseudo-code algorithm. I just want to know if there is any specific computer science theory or it's just something that I have to figure out with a custom method?