Expected gain of a game of chance with differently-priced tokens

Question

Foo and Bar are playing a game of strategy. At the start of the game, there are $N$ apples, placed in a row (in straight line). The apples are numbered from $1$ to $N$. Each apple has a particular price value.

The price of $i$th apple is $p_i$.

In this game, the players Foo and bar make an alternative move.

In each move, the player does the following:

• If there is more than one apple left, the player tosses an unbiased coin. If the outcome is head, the player takes the first apple among the apples that are currently present in a row in a straight line.
• If there is a single apple left, te player takes it.

The goal here is to calculate the expected total price value that Foo will get if Foo plays first.

Example 1:
N=5
Apple price val: 
5 2 3 1 5 

Answer is : 11.00

Example 2:
N=6
7 8 2 3 7 8

Answer : 21.250


Example 3:
N=3
1 4 9

First           Second      Third          Foo Total Val
Foo gets 1  Bar gets 4  Foo gets 9          10
Foo gets 1  Bar gets 9  Foo gets 4          5
Foo gets 9  Bar gets 1  Foo gets 4          13
Foo gets 9  Bar gets 4  Foo gets 1          10

probability 0.5 • 0.5 = 0.25. 
Expected value (Foo)= (0.25 *10 )+ (0.25 *5) + (0.25*13)+ (0.25*10) = 9.500

I wrote the following code:

#include<iostream>
using namespace std;
double calculate(int start,int end,int num,int current);
int arr[2010];
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=0;t<T;t++)
    {
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&arr[i]);
        }
        printf("%.3lf\n",calculate(0,N-1,N/2+N%2,0));   
    }

    return 0;
}
double calculate(int start,int end,int num,int current)
{
    if(num==current)
        return 0;
    double  value=0;
    value=.5*arr[start]+.5*arr[end]+.5*calculate(start+1,end,num,current+1)+.5*calculate(start,end-1,num,current+1);
    return value;
}

But the above code is quite slow. The constraints are: price of apples $p_i \le 1000$; $1 \le N \le 2000$; there are 500 test cases. How can I solve this more efficiently?

Answer 1

They probably meant you to solve it using dynamic programming. Since I'm guessing this is an exercise, I won't say anything more on this front. Also, your program is incorrect: it doesn't consider the actions of Bar.

The game is not really a game of strategy, since there are no choices involved, only chance. In order to compute the expected value that Foo gets, it is enough to compute the probability that Foo takes each particular item. Let $p_{a,b}$ be the probability that Foo takes an item which is the $a$th from the left, $b$th from the right ($a,b \geq 0$, total number of elements is $a+b+1$). Then $$ \begin{align*} p(0,0) &= 1, \\ p(0,1) &= 1/2, \\ p(1,0) &= 1/2, \\ p(1,1) &= 1/2, \\ p(0,b+2) &= 1/2 + p(0,b)/4, \\ p(a+2,0) &= 1/2 + p(a,0)/4, \\ p(1,b+2) &= p(0,b+1)/2 + p(1,b)/4, \\ p(a+2,1) &= p(a+1,0)/2 + p(a,1)/4, \\ p(a+2,b+2) &= (p(a+2,b)+2p(a+1,b+1)+p(a,b+2))/4. \end{align*} $$ You could precompute the requisite values for $a+b+1 \leq 2000$ and then your program will be blazingly fast.

It turns out that for fixed $c$, $p(c,n-c)$ tends to a limit $p_c = 1/2(1 + (-1)^c/3^{c+1})$. To see why, note first that $p_0$ is the ability that if you and a friend alternate tossing fair coins, yours will come up HEAD first. There are many ways to see that $p_0 = 2/3$. Next, we have the formula $p_{c+1} = p_0 (1-p_c) + (1-p_0) p_c$ (exercise), from which the formula for $p_c$ follows by induction.