DIAMOND - Editorial

anton_lunyov · October 15, 2012, 3:00pm

PROBLEM LINK:

Practice
Contest

Author: Kaushik Iska
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

EASY

PREREQUISITES:

Simple Probability, Dynamic Programming

PROBLEM:

Two players play a game on the array of numbers. They make moves alternatively. At each move player can take first or the last number with equal probability. The taken number then removed. Find the expected sum of numbers taken by the first player during the whole game.

QUICK EXPLANATION:

Most of you have found O(N * N) DP solution for this problem. But such solution is too slow since it is not able to find answer for up to 500 tests quickly. To get the fast enough solution one should notice that the answer has the form C[N][1] * V[1] + … + C[N][N] * V[N], where numbers C[N][K] can be found by similar DP as in standard solution. So we get a solution with complexity O(N * N + T * N): O(N * N) for calculating C[N][K] before processing tests and then O(N) for each test.

EXPLANATION:

Denote by V[1], …, V[N] our numbers. Denote by G(i, j) the game described above but played only with numbers V[i], V[i + 1], …, V[j]. Further, denote by E[i][j] the expected sum of numbers taken by the first player during the game G(i, j) and by E2[i][j] the same number but for the second player. Clearly the answer is E[1][N].

We can use dynamic programming to calculate E[i][j]. At first let i = j. Then the first player takes the only available number V[i], so E[i][i] = V[i].

Now let’s i < j. If the first player takes the first number, that is, the number V[i], then we arrive at the game G(i + 1, j) where he is now the second player, so his expected sum is E2[i + 1][j]. Since this happens with probability 1 / 2 this case will add (V[i] + E2[i + 1][j]) / 2 to the expected sum E[i][j]. Similarly if he takes the last number V[j] we should add (V[j] + E2[i][j − 1]) / 2 to the E[i][j]. So we get the formula

**E[i][j] = (V[i] + E2[i + 1][j]) / 2 + (V[j] + E2[i][j − 1]) / 2**.

Let’s get rid of the function E2 in it. For this we note that

**E2[i][j] = V[i] + V[i + 1] + ... + V[j] − E[i][j]**.

Substituting such expressions but for E2[i + 1][j] and E2[i][j − 1] in the formula for E[i][j] we get after straightforward calculations

**E[i][j] = V[i] + ... + V[j] − (E[i + 1][j] + E[i][j − 1]) / 2**.

Precomputing sums S[i] = V[1] + … + V[i] and noting that V[i] + … +V[j] = S[j] − S[i − 1] we arrive at O(N * N) solution for this problem mentioned above which appears to be slow.

To get the fast enough solution let’s analyze this DP solution more carefully. As was mentioned E[i][i] = V[i]. Next we consider E[i][i + 1]. By the main formula we have

**E[i][i + 1] = V[i] + V[i + 1] − (E[i + 1][i + 1] + E[i][i]) / 2 = V[i] + V[i + 1] − (V[i + 1] + V[i]) / 2 = V[i] / 2 + V[i + 1] / 2**.

So E[i][i + 1] = V[i] / 2 + V[i + 1] / 2. Now let’s consider E[i][i + 2]. Again by the main formula and by the formula for E[i][i + 1] obtained just now, which can be used for E[i + 1][i + 2] as well, we get

**E[i][i + 2] = V[i] + V[i + 1] + V[i + 2] − (E[i + 1][i + 2] + E[i][i + 1]) / 2 = V[i] + V[i + 1] + V[i + 2] − (V[i + 1] / 2 + V[i + 2] / 2 + V[i] / 2 + V[i + 1] / 2) / 2 = V[i] * 3 / 4 + V[i + 1] / 2 + V[i + 2] * 3 / 4**.

So E[i][i + 2] = V[i] * 3 / 4 + V[i + 1] / 2 + V[i + 2] * 3 / 4.

We can guess from here that

**E[i][j] = C[L][1] * V[i] + ... + C[L][L] * V[j]**,

where L = j − i + 1 is the length of the current game segment. For example,
C[1][1] = 1,
C[2][1] = 1 / 2, C[2][2] = 1 / 2,
C[3][1] = 3 / 4, C[3][2] = 1 / 2, C[3][3] = 3 / 4.

We can get the recurrent formulas for numbers C[L][k] substituting the formulas for E[i][j], E[i + 1][j] and E[i][j + 1] in terms of C[L][k] in the main recurrent formula for E[i][j]. Watching over the coefficients at each of the numbers V[i], …, V[j] we arrive at the following formula for C[L][k]:

**C[L][k] = 1 − (C[L − 1][k − 1] + C[L − 1][k]) / 2**, for **k** from 1 to **L**,

Where we set for convenience C[L][0] = C[L][L + 1] = 0.

So the solution can be now implemented as follows. At first before reading any data compute numbers C[L][k] for L from 1 to 2000 and for k from 1 to L by the recurrent formulas in a simple double loop. Then for each test read the corresponding sequence of numbers and find the answer by the formula mentioned in the QUICK EXPLANATION. We can even calculate the answer on the fly without saving the sequence of numbers. See setter’s and tester’s solutions for details.

Finally, note that C[L][k] is the probability that first player will take the k-th diamond in the game with L diamonds numbered as 1, 2, …, L. Thanks to pragrame for mentioning that. Also see the corresponding comment in author’s solution.

ALTERNATIVE SOLUTION:

The problem can be solved without exploiting the relation between E[i][j] and E2[i][j]. Instead one should obtain similar recurrence for E2[i][j]. And then both these values can be expressed as linear combinations of numbers V[i], …, V[j] with some coefficients, for which some similar recurrent formulas as for our coefficients C[L][k] can be obtained. But such solution requires twice more memory. Also it is quite long to describe it in the same details as the previous one. Hence see as a reference the following solution by ballon_ziq.

There exist even more complex solutions. Check it out, for example, this solution by acube. Hats off to the person who will understand this solution

AUTHOR’S AND TESTER’S SOLUTIONS:

Autho’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

Game - 2 (In Russian only)

betlista · October 15, 2012, 3:21pm

Hm, I thought that using double is not ok in this problem…

pujarirajkumar · October 15, 2012, 4:00pm

I think the recurrence is E[i][j]= (V[i]+E[i+1][j])/2 + (V[j]+E[i][j-1])/2. It is E[i][j+1] instead of E[i][j-1] in the 2nd part of RHS in the original editorial.

vinayak_garg · October 15, 2012, 4:17pm

I visualized prefixes (for multiplication with values) something like this->

alt text

First without denominators, then with them.

This is essentially

d[i][j] = d[i][j-1] + (d[i-1][j-2] - d[i-1][j])/2;

For second column it is

d[i][1] = d[i][0] - d[i-1][1]/2;

Also being symmetric, only half columns need to be computed.

And first column is easy to find

And thankfully all this worked out in double.

bishop · October 15, 2012, 8:27pm

i think my solution is similar to acube’s … and i exploited pascal triangle a bit to generate answers, i found the pattern by brute forcing for N 1 to 10
my soln : CodeChef: Practical coding for everyone

pragrame · October 15, 2012, 9:36pm

My solution is essentially the same as the Editorialist explanation: Generate C[N][K] for all N, K, and then do Sum(C[N][i] * V[i]). However, I’d like to give my interpretation of C[N][j] as : Probability of 1st player getting the j’th diamond in a game of 1,2,…,N diamonds. (I don’t worry about manipulating the expression got for expectations etc.)

The rest is pretty much the same: with 0.5 prob you pick the first diamond, and are left with (1 - prob other player gets the j-1’th diamond), or with prob 0.5 you pick the last diamond and are left with (1 - prob other player gets the j’th diamond).

So, you are really left with C[N][j] = 0.5 * (1 - C[N-1][j] + 1 - C[N-1][j-1]).

The special cases of C[N][0] (or C[N][N-1]) are handled as 0.5 * prob you get the diamond + 0.5 * (1 - prob other player gets the diamond), thats 0.5 * (1 + 1-C[N-1][0]).

It was a really nice problem once you got the solution. Good job, setter!

acube · October 16, 2012, 4:11am

My solution is not as hard as it seems :). The idea is the following:

Let indexes start from 1. For each element V[i], let’s consider all segments that start at i (i…r) and end at i (l…i). So we now have two cases to consider, but it’s enough to consider one, as the other one is similar:

For some fixed R, what is the probability that we will get the segment (i…R) left? It’s equal to G(i, R) = C(i-1 + N-R, N-R)/2^(i-1 + N-R) [we took N-R elements from the right and i-1 elements from the left -> amount of combinations is simply C(tot. elements, el. from right/left) and total amount of outcomes after (i-1 + N-R) moves is 2^(i-1 + N-R)]. So in general G(i, j) = C(i, j)/2^i.
Not all R are suitable as (R-i+1) mod 2 = N mod 2 (since we play first).
So the answer when i is the left end of a segment should be:
For even N: G(i, i+1) + G(i, i+3) + G(i, i+5) + …
For odd N: G(i, i) + G(i, i+2) + G(i, i+4) + …
And this is simply sum of odd/even rows for a specified column. Which could be calculated using partial sums for each column.

quark17 · October 16, 2012, 5:22pm

I did the same thing O(N^2) Pre-processing and O(N) for queries.

Could you tell why my repeated attempts to submit this were given a “TLE” ?

Here is one such attempt: CodeChef: Practical coding for everyone

udaysagar · October 17, 2012, 12:27am

WHEN I WRITE THE BELOW TWO STATEMENTS INSIDE MAIN…ITS GIVING ME A RUN TIME ERROR(SIGSEGV)
BUT WHY???

#include <stdio.h>

double prob[2001][2001];

int i, j;

int main() {

    int nt, n, ha;
    double ans = 0.0;
    for(i=1; i < 2001; i++) {
        for(j = 1; j <= i;j++) {
            prob[i][j] = 1.0 - 0.5 * (prob[i-1][j] + prob[i-1][j-1]);
        }
    }
    scanf("%d",&nt);
    while(nt--) {
        ans = 0.0;
        scanf("%d",&n);
        for(i=1;i<=n;i++) 	{
	    scanf("%d",&ha);
            ans += prob[n][i] * ha; 	}
        printf("%.6lf\n",ans);
    }
    return 0;
}

JACOB_SUNNY · October 2, 2014, 7:10pm

Is a recursive method inefficient as compared to the matrix method ?

phanindhar · October 15, 2012, 3:36pm

Even me…!!

anton_lunyov · October 15, 2012, 3:39pm

Well, I made a cross-check using BigInteger, and double find C[N][K] for all N and K with normal accuracy 14-15 significant digits. So it really works.

anton_lunyov · October 15, 2012, 3:40pm

It is already working

betlista · October 15, 2012, 3:41pm

thanks, I retried and link was ok, so I removed comment

anton_lunyov · October 15, 2012, 4:13pm

Thanks. It is already fixed.

n2n · October 15, 2012, 9:09pm

You could do it without float or double. My soln: CodeChef: Practical coding for everyone

betlista · October 16, 2012, 6:03pm

My first tip is, that you are using cin and cout, do you realize, that you want to load 500*20.000*~4 bytes in worst case?

edit: My tip was good, when I replaced cin with scanf I got WA - CodeChef: Practical coding for everyone

quark17 · October 16, 2012, 10:09pm

WA was for precision error. I’ve fixed it.
Now, what’s the deal with a 17.76sec ‘Accepted’ ? here- CodeChef: Practical coding for everyone

Aren’t the submissions being judged with time limit now?

betlista · October 16, 2012, 10:13pm

They are, but time 17.76s is summary time for all test cases.

quark17 · October 16, 2012, 10:35pm

Oh, I see.

I shall be more careful about cins’ couts’ from the next time. Thanks a lot for your inputs.