InterviewStreet (Vertical Sticks) just a tip where to get started

Question

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?

Answer 1

I haven't coded and tested it, but I'm pretty sure basic probabilistic methods can solve this problem.

I'm not sure how large a hint you want, so I'll keep it cryptic. If you need more help, just add a comment.

Use linearity of expectation, sum over all positions and then sum over all values. Bayes' theorem and some counting will do the last bit.

Every step is a basic probabilistic trick, so in a way it's a specific part of computer science, but on the other hand you'll have to apply the steps to the problem in a custom way. I hope that answers your question.

Answer 2

There is a solution posted on http://www.mitbbssg.com/article_t/JobHunting/32011987.html I did not understand though what is the solution :

Following is the english translation :

: Just accepted. Calculate expected value for every position and sum up all.
: Pos_1: expected value = 1.00
: Pos_2: expected value = Sum of {if it is y_i, then how many chance of
: Length
: 1 * 1, how many chance of length 2 * 2, how ...} / N
: Ans = Sum {Pos_i | for all position i}

/ / D [i], input
double solve () {
    double ans = 1.0;
    for (int pos = 2; pos <= N; pos + +) {
        double t1 = 0.0;
        for (int i = 0; i <N; i + +) {/ / choose i in position pos
            int x = C [i] [0]; / / <D [i]
            int y = C [i] [1]; / /> = D [i]

            double pre = 1.0;
            int k = 1;
            for (; k <= (pos - 1); k + +) {
                double t2 = pre * ((double) y / (double) (x + y));
                t1 + = (t2 * k);
                pre *= ((double) x / (double) (x + y));
                if (x - == 0)
                    break;
            }
            if (k == pos)
                t1 + = (pre * pos);
        }
        ans + = (t1 / N);
    }
    return ans;
}

I came up with complete code with this solution but it does not work. my assumption are x and y are the co-ordinates of the points.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>

class Vertical_Sticks {
public:
    Vertical_Sticks() {
    }
    ~Vertical_Sticks(){
    }
    void Solve() {
        int T;
        std::cin >> T;
        std::vector<double> answers;
        for ( int t = 0; t < T; t++) {
            int N;
            std::cin >> N; 
            std::vector<std::vector<int> > C(N,std::vector<int>(2));
            for ( int i = 0; i < N; i++ ){
                int v;
                std::cin >> v;
                C[i][0] = i + 1;
                C[i][1] = v;
            }
            double ans = 1.0;
            for (int pos = 2; pos <= N; pos++) {
                double t1 = 0.0;
                for (int i = 0; i < N; i++) {
                    int x = C[i][0];
                    int y = C[i][1];

                    double pre = 1.0;
                    int k = 1;
                    for (; k <= (pos - 1); k++) {
                        double t2 = pre * ((double)y/(double)(x + y));
                        t1 += (t2 * k);
                        pre *= ((double)x/(double)(x + y));
                        if (x-- == 0)
                            break;
                    }
                    if (k == pos)
                        t1 += (pre * pos);
                }
                ans += (t1 / N);
            }
            answers.push_back(ans);
        }
        std::cout.setf(std::ios::fixed);
        std::cout.precision(2);
        for ( std::vector<double>::iterator it = answers.begin(); it != answers.end(); ++it) {
            std::cout << *it << std::endl;
        }

    }
};
int main ( int argc, char **argv) {
    Vertical_Sticks vs;
    vs.Solve();
    return 0;
}

and the Input is

6
3
1 2 3
3
3 3 3
3
2 2 3
4
10 2 4 4
5
10 10 10 5 10
6
1 2 3 4 5 6