chelsea - 1 year ago 26

Java Question

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

Answer

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;
if(already calculated this state)
return dp[player][start][end];
double result= 0;
if(player == 0){
result = 0.5*( set[start] + f(1, start + 1,end) ) + 0.5*(set[end] + f(1,start, end - 1));
}else{
result = 0.5*( f(0, start + 1,end) ) + 0.5*(f(0,start, end - 1));
}
return dp[player][start][end] = result;
}
```