Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
So V is an array of the sums of v1 ... vn? Then surely Vni is just its position on the x axis? Or have I missed something here? ie for the v2 above V[y2] = 1 + 1 –  adrianmcmenamin Dec 26 '11 at 19:39
    
It looks like V is a function whose input is any permutation of Y. The output of the function is the sum of v1...vn, v1...vn being the length of ray shot out at each position of our current permutation of Y. Given Y(1, 2, 3), v=(1, 2, 3) and V(Y) = 6 (max sum of rays) Given Y(3,1,2), v=(1, 1, 2) and V(Y) = 4 Given Y(3,2,1), v=(1, 1, 1) and V(Y) = 3 (min sum of rays) The brute force approach would be to find V(Y) for all permutations of Y and take the average. (brute force probably won't work for the challenge, N! gets huge fast. Not sure what the optimal algo would be) –  Jason McClellan Dec 27 '11 at 9:05

2 Answers 2

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.

share|improve this answer
    
Yes, please help me to understand algorithm –  Avinash Dec 29 '11 at 11:57

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
share|improve this answer
    
Not sure what C or D are here. –  Jason McClellan Dec 28 '11 at 8:50
1  
I think I get the idea, but not sure it works or if I actually understand it. Essentially, for each position, you figure out the chances that every value of Y will have a length of 1, 2, 3, etc. (up to the max length for that position, which is the position number itself) and divide that value by the total number of values in Y. Then, summing all of those values will (apparently) give you the answer. Hm.. –  Jason McClellan Dec 28 '11 at 8:52
    
I'm trying to understand what this code is doing, and I can't see how the expression 'x+y' can possibly mean something: you add a length of a stick to its position in the input, which are two unrelated values, unless I'm missing something. Does anyone understand this bit? –  Alex ten Brink Dec 28 '11 at 16:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.