Sum this up:
PROBLEM LINK:
Contest: Code Drive
Author: Satyarth Pandey
Tester: Lavish Gupta , Takuki Kurokawa
DIFFICULTY:
EASY
PREREQUISITES:
Linearity of expectation
PROBLEM:
You are given an array A with N positive elements A_1, A_2, \dots, A_N. You are also given a function S on any array C with length N defined as follow:
S(C) = \sum\limits_{i=1}^{N}(\dfrac{C_{i-1} + C_{i+1}}{2}-C_i)
Note that conventionally, we define all elements outside the range of the array to have value 0. In this context, C_0 = C_{N + 1} = 0.
Consider the following process:
- Choose a permutation P of values from 1 to N uniformly randomly.
- Let B be the array of N elements B_1, B_2, \dots, B_N, where B_i = A_{P_i}.
Define V as the expected value of |S(B)|. Find \lfloor V \rfloor.
Note :
- |X| denotes absolute value of X
- \lfloor X \rfloor is the greatest integer that does not exceed X.
QUICK EXPLANATION:
The answer is the average of given elements of array A.
EXPLANATION:
Let’s simplify the given summation. Let’s call the i^{th} term of given summation - S(C) as Term_{i} and find the contribution of each element in given summation:
-
C_1 gets subtracted once in Term_{1} and added \frac{1}{2} times in Term_2.
-
C_{N} gets subtracted once in Term_{N} and added \frac{1}{2} times in Term_{N-1}.
-
C_{i} gets subtracted once in Term_{i} , but added \frac{1}{2} times in Term_{i-1} and \frac{1}{2} times in Term_{i+1}. (if i>1 and i<N)
We can see that only the first and last element contribute in S(C) and others get cancelled out.
Formally, for array C :-
S(C) = -\dfrac{1}{2}\times(C_1+C_{N})
Now, Calculating the Expected Value of S(B) for array B described in problem :
S(B) = -\dfrac{1}{2}\times(B_1+B_{N})
As all elements of A are positive,
|S(B)| = \dfrac{1}{2}\times(B_1+B_{N})
E(|S(B)|) = E (\dfrac{1}{2}\times(B_1+B_{N}))
E(|S(B)|) = \dfrac{1}{2}\times E (B_1+B_{N})
Using Linearity of Expectation:
E(|S(B)|) = 1/2\times(E (B_1)+E(B_{N}))
E(B_1) and E(B_{N}) are both just the average of given array.
Let Avg(A) = \dfrac{\sum\limits_{i=1}^{N}{A_i}}{N}
Then,
E(|S(B)|) = \dfrac{1}{2} \times (Avg(A)+Avg(A))
E(|S(B)|) = Avg(A)
For simplicity, only the floor value of E(|S(B)|) is required as output.
SOLUTIONS:
Setter’s Solution
#include "bits/stdc++.h"
using namespace std;
void solve()
{
int n;
cin >> n;
long long sum = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
sum += x;
}
cout << sum / n << "\n";
}
int main()
{
int tt = 1;
cin >> tt;
for (int i = 1; i <= tt; i++)
solve();
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
long long s = accumulate(a.begin(), a.end(), 0LL);
s /= n;
cout << s << '\n';
}
return 0;
}
