### PROBLEM LINK:

**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

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

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

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]**:

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)