EVOFWEIRDSUM - Editorial

Sum this up:

PROBLEM LINK:

Practice

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;
}

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.
@satyacoder

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)

Similarly

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

1 Like

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.

2 Likes

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

2 Likes

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

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

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

V=\frac{\sum_{j=1}^{N!}S(P_j)}{N!}

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)}

V=\frac{Z}{N}

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

3 Likes

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)!

can anyone help why this shows WA for last two test cases, its the same ans according to editorial logic
https://www.codechef.com/viewsolution/55661168

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