PROBLEM LINK:
Author: artha6391
Tester: anushka_nagar
Editorialist: Mayur Paliwal
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] * P[1] + … + C[N][N] * P[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 P[1], …, P[N] our numbers. Denote by G(i, j) the game described above but played only with numbers P[i], P[i + 1], …, P[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 P[i], so E[i][i] = P[i].
Now let’s i < j. If the first player takes the first number, that is, the number P[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 (P[i] + E2[i + 1][j]) / 2 to the expected sum E[i][j]. Similarly if he takes the last number P[j] we should add (P[j] + E2[i][j − 1]) / 2 to the E[i][j]. So we get the formula
E[i][j] = (P[i] + E2[i + 1][j]) / 2 + (P[j] + E2[i][j − 1]) / 2.
Let’s get rid of the function E2 in it. For this we note that
E2[i][j] = P[i] + P[i + 1] + … + P[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] = P[i] + … + P[j] − (E[i + 1][j] + E[i][j − 1]) / 2.
Precomputing sums S[i] = P[1] + … + P[i] and noting that P[i] + … +P[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] = P[i]. Next we consider E[i][i + 1]. By the main formula we have
E[i][i + 1] = P[i] + P[i + 1] − (E[i + 1][i + 1] + E[i][i]) / 2 = P[i] + P[i + 1] − (P[i + 1] + P[i]) / 2 = P[i] / 2 + P[i + 1] / 2.
So E[i][i + 1] = P[i] / 2 + P[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] = P[i] + P[i + 1] + P[i + 2] − (E[i + 1][i + 2] + E[i][i + 1]) / 2 = P[i] + P[i + 1] + P[i + 2] − (P[i + 1] / 2 + P[i + 2] / 2 + P[i] / 2 + P[i + 1] / 2) / 2 = P[i] * 3 / 4 + P[i + 1] / 2 + P[i + 2] * 3 / 4.
So E[i][i + 2] = P[i] * 3 / 4 + P[i + 1] / 2 + P[i + 2] * 3 / 4.
We can guess from here that
E[i][j] = C[L][1] * P[i] + … + C[L][L] * P[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 P[i], …, P[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 Cube in the game with L Cubes numbered as 1, 2, …, L.
SOLUTIONS:
Setter's Solution
#include <stdio.h>
#define maxn 2222
double prob[maxn][maxn];
int i, j;
void init() {
for(i=1; i < maxn; i++) {
for(j = 1; j<= i;j++) {
prob[i][j] = 1.0 - 0.5 * (prob[i-1][j] + prob[i-1][j-1]);
}
}
return;
}
int a[maxn];
int main() {
int nt, n;
init();
scanf(“%d”,&nt);
while(nt–) {
double ans = 0.0;
scanf(“%d”,&n);
for(i=1; i<=n; i++)
scanf(“%d”,&a[i]);
for(i=1;i<=n;i++)
ans += prob[n][i] * a[i];
printf(“%.6lf\n”,ans);
}
return 0;
}
Tester's Solution
#include <stdio.h>
#define maxn 2222
double prob[maxn][maxn];
int i, j;
void init() {
for(i=1; i < maxn; i++) {
for(j = 1; j<= i;j++) {
prob[i][j] = 1.0 - 0.5 * (prob[i-1][j] + prob[i-1][j-1]);
}
}
return;
}
int a[maxn];
int main() {
int nt, n;
init();
scanf(“%d”,&nt);
while(nt–) {
double ans = 0.0;
scanf(“%d”,&n);
for(i=1; i<=n; i++)
scanf(“%d”,&a[i]);
for(i=1;i<=n;i++)
ans += prob[n][i] * a[i];
printf(“%.6lf\n”,ans);
}
return 0;
}
Editorialist's Solution
#include <stdio.h>
#define maxn 2222
double prob[maxn][maxn];
int i, j;
void init() {
for(i=1; i < maxn; i++) {
for(j = 1; j<= i;j++) {
prob[i][j] = 1.0 - 0.5 * (prob[i-1][j] + prob[i-1][j-1]);
}
}
return;
}
int a[maxn];
int main() {
int nt, n;
init();
scanf(“%d”,&nt);
while(nt–) {
double ans = 0.0;
scanf(“%d”,&n);
for(i=1; i<=n; i++)
scanf(“%d”,&a[i]);
for(i=1;i<=n;i++)
ans += prob[n][i] * a[i];
printf(“%.6lf\n”,ans);
}
return 0;
}