PROBLEM LINK:Author: Kaushik Iska 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 Let's get rid of the function E2 in it. For this we note that 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 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 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 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 where L = j − i + 1 is the length of the current game segment. For example, 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]: 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 kth 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. RELATED PROBLEMS:Game  2 (In Russian only)
This question is marked "community wiki".
asked 15 Oct '12, 15:00

I visualized prefixes (for multiplication with values) something like this> First without denominators, then with them. This is essentially
For second column it is
Also being symmetric, only half columns need to be computed. And first column is easy to find :) And thankfully all this worked out in answered 15 Oct '12, 16:17

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:
link
This answer is marked "community wiki".
answered 16 Oct '12, 04:11

I think the recurrence is E[i][j]= (V[i]+E[i+1][j])/2 + (V[j]+E[i][j1])/2. It is E[i][j+1] instead of E[i][j1] in the 2nd part of RHS in the original editorial. answered 15 Oct '12, 16:00

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 answered 15 Oct '12, 20:27

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 j1'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[N1][j] + 1  C[N1][j1]). The special cases of C[N][0] (or C[N][N1]) are handled as 0.5 * prob you get the diamond + 0.5 * (1  prob other player gets the diamond), thats 0.5 * (1 + 1C[N1][0]). It was a really nice problem once you got the solution. Good job, setter! answered 15 Oct '12, 21:36

Hm, I thought that using double is not ok in this problem... answered 15 Oct '12, 15:21
2
Even me...!!
(15 Oct '12, 15:36)
1
Well, I made a crosscheck using BigInteger, and double find C[N][K] for all N and K with normal accuracy 1415 significant digits. So it really works.
(15 Oct '12, 15:39)
You could do it without float or double. My soln: http://www.codechef.com/viewsolution/1404891
(15 Oct '12, 21:09)

I did the same thing O(N^2) Preprocessing 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 answered 16 Oct '12, 17:22
My first tip is, that you are using edit: My tip was good, when I replaced
(16 Oct '12, 18:03)
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)
They are, but time 17.76s is summary time for all test cases.
(16 Oct '12, 22:13)
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)

WHEN I WRITE THE BELOW TWO STATEMENTS INSIDE MAIN....ITS GIVING ME A RUN TIME ERROR(SIGSEGV)
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[i1][j] + prob[i1][j1]); } } 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; } answered 17 Oct '12, 00:27
1
This solution get AC:
(17 Oct '12, 02:46)

Is a recursive method inefficient as compared to the matrix method ? answered 02 Oct '14, 19:10

It is already working :)
thanks, I retried and link was ok, so I removed comment ;)