Sum this up:



Contest: Code Drive

Author: Satyarth Pandey

Tester: Lavish Gupta , Takuki Kurokawa




Linearity of expectation


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.


The answer is the average of given elements of array A.


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}


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.


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++)
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#define debug(...)

int main() {
    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;

1 Like

I was upsolving it , I found this expression as the final answer

((n!-(n-1))/(2(n!)))* sum where sum is the sum of array elements .

But how can I simplify it to average can please someone point out.

Can you describe, how you obtained this expression? I don’t think it’s correct.

1 Like

yeah sure !

lets consider for n=3
I m not taking the division by 2 initially , I will consider it in the end.
So the S_i becomes a_{i-1} + a_{i+1} - 2 a_{i}

All possible permutations :

a_1, a_2 ,a_3
a_1, a_3 ,a_2
a_2, a_1 ,a_3
a_2, a_3 ,a_1
a_3, a_1 ,a_2
a_3, a_2 ,a_1

Now I was considering the first permutation and was concluding the result for the other permutations by symmetric behavior.

First permutation {a_1}, {a_2}, {a_3}

S_1 = 0 + a_2 - 2 a_1 + a_1 + a_3 - 2 a_2 + a_2 - 2 a_3+0
S_1 = -(a_1+ a_3)

Now from symmetric properties we can say that for the 2nd permutation
a_1, a_3 ,a_2

S_2 = -(a_1+ a_2)


S_3 = - (a_2 + a_3)
S_4 = -(a_2 + a_1)
S_5 = -(a_3 + a_2)
S_6 = -(a_3 + a_1)

S_1 + S_2 + S_3 + S_4 + S_5 + S_6 = -4( a_1 + a_2 + a_3 + a_4 + a_5 + a_6)

abs( \sum\limits_{i=1}^{6} S_i ) = 4( a_1 + a_2 + a_3 + a_4 + a_5 + a_6)

here 4 is bascially 2(n-1)!

so E(x) = ((2(n-1)!) \sum\limits_{i=1}^{n} A_i) / (n!)

and we need to divide the final result by 2 as well
so E(x)/=2

Update I made a mistake before so I fixed it , thanks @master_mind14


This is a very simple problem if you just simplify the statement. For any array C we essentially have S(C) = -\dfrac{C_1+C_n}{2}. Since we only deal with absolute value and all elements of the array are positive, we can ignore the -1. Then by Linearity the expected value of \dfrac{B_1+B_n}{2} is just sum of all the elements of A divided by n. Thus, if s is the sum of all elements of A, then the answer is \lfloor s/n\rfloor.


Why did you assume that the 4 you got is (n! - (n - 1)), I’d say it is 2 * (n - 1)!.


S(C) = \sum_{i=1}^{N}{\frac{C_{i-1}+C_{i+1}}{2}-C_i}{}

Upon expanding it, we can see

S(C) = \frac{C_0+C_2}{2}-C_1+\frac{C_1+C_3}{2}-C_2+...+\frac{C_{N-1}+C_{N+1}}{2}-C_N

As given in Problem statement - C_0=C_N=0

S(C) = \frac{C_2}{2}-C_1+\frac{C_1+C_3}{2}-C_2+...+\frac{C_{N-1}}{2}-C_N

Let us say C_1+C_2+C_3+...+C_N=Z (Summation of Array elements).

S(C) = \frac{C_1+2C_2+2C_3+..+2C_{n-1}+C_N}{2}-Z

S(C) = \frac{2C_1+2C_2+2C_3+..+2C_{n-1}+2C_N}{2}-Z-\frac{C_1+C_N}{2}

S(C) = \frac{2Z}{2}-Z-\frac{C_1+C_N}{2}

S(C) = -\frac{C_1+C_N}{2}

Since C_i\gt0 for all 1\le i\le N, and we want only absolute values


As for the expected value calculation, Here is one more mathematical proof.

We want an expected value of S(B) over all possible permutation of B. If a permutation of B can be denoted as P_j, then expected values


To find all the permutation, there are total N!, we can use a property that we obtained above. Since S(C)=\frac{C_1+C_N}{2}, We can generalize the permutations.

All permutations, which are of P_1,P_x....P_y,P_N will give ans S(C)=\frac{C_1+C_N}{2}

P_1,P_x....P_y,P_2 gives S(C)=\frac{C_1+C_2}{2}

P_1,P_x....P_y,P_3 gives S(C)=\frac{C_1+C_3}{2}

Each of these permutations occur (N-2)! times.

To sum up for P_1, we can write

\frac{(n-2)!\times (C_1+C_2)}{2}+\frac{(n-2)!\times (C_1+C_3)}{2}+\frac{(n-2)!\times (C_1+C_4)}{2}+..+\frac{(n-2)!\times (C_1+C_N)}{2}

=> \frac{(N-2)!}{2}[(N-1)C_1+Z-C_1]

=> \frac{(N-2)!}{2}[Z+(N-2)C_1]

Similiary, for C_2,C_3 and so on,

=> \frac{(N-2)!}{2}[Z+(N-2)C_i]

Adding them all together, we get value of \sum_{j=1}^{N!}S(P_j)

=> \frac{(N-2)!}{2} [NZ+(N-2)Z]

V=\frac{\frac{(N-2)!}{2} [NZ+(N-2)Z]}{N!}

V=\frac{ [NZ+(N-2)Z]}{2N(N-1)}

V=\frac{ Z(2N-2)}{2N(N-1)}


Then we get just get the floor value of \frac{Z}{N} as our answer.


I think maybe I m wrong in this part. Thanks for pointing this out. And please can u tell how u figured our this.
Update : I understood where I went wrong.
Each number occurs (n-1)! in single column and now we intrested with the first and last column so 2*(n-1)!

1 Like

can anyone help why this shows WA for last two test cases, its the same ans according to editorial logic

Your sum variable is overflowing int. You should use long long instead.

1 Like

@satyacoder why we are using floor of (s/n) and not ceil of (s/n)

Because the problem asked to output the floor value of expected value :slight_smile:

Nicely explained!!

Your welcome! :grinning_face_with_smiling_eyes: