chelsea - 2 years ago 57
Java Question

# Listing the total sum of all possibe sums in a set with constraints

I am keen to find out the following:

Given a set with N elements, my friend and I are playing a game.I always make the first move.
We can only remove either the first or the last element with 50% chance each.We take alternate turns in the game.If only one element remains,we can remove it for sure.What is the expected sum that I can collect?

``````For example:N=2 {10,20} Possible sets that I can collect are {10},{20}.
So expected sum is 0.5*10+0.5*20=15.
``````

My approach:

Since probability of getting a possible sum is equal in all cases,we only need to compute the sum of all possible sums and then multiply it by (0.5)^N/2.

I tried to use recursion to compute the required sum:

``````f(i,j)-computes the sum between i and j recursively
f(i,j)=2*a[i]+func(i,j-2)+func(i+1,j-1)+func(i+1,j-1)+func(i+2,j)+2*a[j]);
Initial call f(1,N)
``````

But the approach doesn't seem to work. What should I do?

Complete function is below:

``````class CandidateCode {
static long v[][] = new long[1003][1003];

public static long func(int a[], int i, int j) {
if (i == j)
return v[i][j] = a[i];
if (v[i][j] != 0)
return v[i][j];
else {
if (i > j - 2 && i + 1 > j - 1 && i + 2 > j)
return (v[i][j] += 2 * a[i] + 2 * a[j]);
else
return (v[i][j] += 2 * a[i] + func(a, i, j - 2) + func(a, i + 1, j - 1) + func(a, i + 1, j - 1)
+ func(a, i + 2, j) + 2 * a[j]);
}
}

public static void main(String args[]) {
int n;
int a[] = { 0, 6, 4, 2, 8 };
n = a.length - 1;
System.out.println(func(a, 1, 4) / Math.pow(2, n / 2));
}
}
``````

Actual link to the problem is here:

http://stackoverflow.com/questions/25760440/calculating-mathematical-expectation-of-given-data?noredirect=1#comment40288068_25760440

This problem can be solved by applying dynamic programming.

First, we have the state of the game is `(player ,start, end)` ,which indicates the current player, and the range of values that's available in the original set. At the beginning, we start at player 0 and `start` is 0, `end` is N - 1.

Denote that the first player is 0 and the second player is 1, we have the expected value of player 0:

`````` if(player == 0){
double result = 0.5*( set[start] + f(1, start + 1,end) ) + 0.5*(set[end] + f(1,start, end - 1));
}else{
double result = 0.5*( f(0, start + 1,end) ) + 0.5*(f(0,start, end - 1));
}
``````

So for each state, we can store all calculated state in a `dp[player][start][end]` table, which reduce the time complexity to O(2*N*N) with N is number of value in set.

Pseudo code:

`````` double expectedValue(int player, int start, int end, int[]set){
if(start == end)
if(player == 0)
return set[start];
return 0;