You are not logged in. Please login at www.codechef.com to post your questions!

×

DIAMOND - Editorial

13
4

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)

This question is marked "community wiki".

asked 15 Oct '12, 15:00

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138
accept rate: 12%

edited 18 Oct '12, 15:04

It is already working :)

(15 Oct '12, 15:40) anton_lunyov ♦6★

thanks, I retried and link was ok, so I removed comment ;-)

(15 Oct '12, 15:41) betlista ♦♦3★

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.

link

answered 15 Oct '12, 16:17

vinayak%20garg's gravatar image

4★vinayak garg
3.7k113249
accept rate: 18%

edited 15 Oct '12, 16:19

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:

  1. 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.
  2. Not all R are suitable as (R-i+1) mod 2 = N mod 2 (since we play first).
  3. 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.
link
This answer is marked "community wiki".

answered 16 Oct '12, 04:11

acube's gravatar image

5★acube
14
accept rate: 0%

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.

link

answered 15 Oct '12, 16:00

pujarirajkumar's gravatar image

3★pujarirajkumar
3115
accept rate: 0%

edited 15 Oct '12, 16:00

Thanks. It is already fixed.

(15 Oct '12, 16:13) anton_lunyov ♦6★

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 : http://www.codechef.com/viewsolution/1402473

link

answered 15 Oct '12, 20:27

bishop's gravatar image

2★bishop
313
accept rate: 0%

edited 15 Oct '12, 20:28

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!

link

answered 15 Oct '12, 21:36

pragrame's gravatar image

6★pragrame ♦♦
973568379
accept rate: 14%

edited 15 Oct '12, 21:36

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

link

answered 15 Oct '12, 15:21

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

2

Even me...!!

(15 Oct '12, 15:36) phanindhar3★
1

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.

(15 Oct '12, 15:39) anton_lunyov ♦6★

You could do it without float or double. My soln: http://www.codechef.com/viewsolution/1404891

(15 Oct '12, 21:09) n2n_5★

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: http://www.codechef.com/viewsolution/1439642

link

answered 16 Oct '12, 17:22

quark17's gravatar image

2★quark17
1
accept rate: 0%

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 - http://www.codechef.com/viewsolution/1480144

(16 Oct '12, 18:03) betlista ♦♦3★

WA was for precision error. I've fixed it. Now, what's the deal with a 17.76sec 'Accepted' ? here- http://www.codechef.com/viewsolution/1480419

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

(16 Oct '12, 22:09) quark172★

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

(16 Oct '12, 22:13) betlista ♦♦3★

Oh, I see.

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

(16 Oct '12, 22:35) quark172★

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;
}
link

answered 17 Oct '12, 00:27

udaysagar's gravatar image

1★udaysagar
1
accept rate: 0%

edited 17 Oct '12, 02:45

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138

1

This solution get AC:
http://www.codechef.com/viewsolution/1480824
What is the problem?

(17 Oct '12, 02:46) anton_lunyov ♦6★

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

link

answered 02 Oct '14, 19:10

JACOB%20SUNNY's gravatar image

0★JACOB SUNNY
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,487
×3,212
×1,790
×15
×4

question asked: 15 Oct '12, 15:00

question was seen: 7,270 times

last updated: 02 Oct '14, 19:10