1
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Please don't post long blurbs of real code and restrict yourself to pseudocode which highlights the central ideas of the algorithm. You can put your full code on pastebin.com or similar, if you think it can be useful for others, and link to it; your post should not rely on its availability, though. $\endgroup$ – Raphael Oct 6 '12 at 14:34
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. When your question has code, it's probably off-topic here and should be on Stack Overflow; we can help you with the algorithm, however. For help with code, ask on Stack Overflow. $\endgroup$ – Gilles 'SO- stop being evil' Oct 6 '12 at 20:33
  • 2
    $\begingroup$ @Raphael Please do not recommend using external sites that may become inaccessible and may expire content. All relevant material should be on the site. The code does not belong here at all; Chopra: please describe the algorithm in a way that doesn't require the reader to know C++. $\endgroup$ – Gilles 'SO- stop being evil' Oct 6 '12 at 20:45
  • 3
    $\begingroup$ @Gilles: disagree with your claim that if the question involves code then it's off-topic. The question isn't about the code, it's about the algorithm. You only have to read one line to realize the OP was computing the expected value in the naive recursive way rather than using dynamic programming. $\endgroup$ – Yuval Filmus Oct 6 '12 at 22:29
  • 1
    $\begingroup$ @Yuval, Gilles is right, the policy here is that algorithms should be described in a way that is accessible to people who are not familiar with a particular language as Gilles wrote. $\endgroup$ – Kaveh Oct 9 '12 at 3:25
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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