Sum this up solution codechef

Sum this up solution codechef

 

You are given an array AA with NN positive elements A1,A2,,ANA1,A2,…,AN. You are also given a function SS on any array CC with length NN defined as follow:

S(C)S(C) = i=1N(Ci1+Ci+12Ci)∑i=1N(Ci−1+Ci+12−Ci)

Note that conventionally, we define all elements outside the range of the array to have value 00. In this context, C0=CN+1=0C0=CN+1=0.

Consider the following process:

  • Choose a permutation PP of values from 11 to NN uniformly randomly.
  • Let BB be the array of NN elements B1,B2,,BNB1,B2,…,BN, where Bi=APiBi=APi.

Define VV as the expected value of |S(B)||S(B)|. Find V⌊V⌋.

Note :

  • |X||X| denotes absolute value of XX
  • X⌊X⌋ is the greatest integer that does not exceed XX.

Input Format

  • The first line of the input contains an integer TT – the number of test cases. The test cases then follow.
  • The first line of each test case contains an integer NN – the size of array.
  • The second line of each test case contains NN integers A1,A2,,ANA1,A2,…,AN – the elements of the array.

Output Format

For each testcase, output V⌊V⌋ in a new line.

Constraints

  • 1T101≤T≤10
  • 1N21051≤N≤2⋅105
  • 1Ai21051≤Ai≤2⋅105

Sample Input 1 

2
2
1 1
3
8 2 2

Sample Output 1 

1
4

Explanation

  • Test case 22:
    • With P=[1,2,3]P=[1,2,3] or P=[1,3,2]P=[1,3,2], we obtain B=[8,2,2]B=[8,2,2], which has |S(B)|=|(0+228)+(8+222)+(2+022)|=5|S(B)|=|(0+22−8)+(8+22−2)+(2+02−2)|=5.
    • With P=[2,1,3]P=[2,1,3] or P=[3,1,2]P=[3,1,2], we obtain B=[2,8,2]B=[2,8,2], which has |S(B)|=|(0+822)+(2+228)+(8+022)|=2|S(B)|=|(0+82−2)+(2+22−8)+(8+02−2)|=2.
    • With P=[2,3,1]P=[2,3,1] or P=[3,2,1]P=[3,2,1], we obtain B=[2,2,8]B=[2,2,8], which has |S(B)|=|(0+222)+(2+822)+(2+028)|=5|S(B)|=|(0+22−2)+(2+82−2)+(2+02−8)|=5.

Therefore V=5+5+2+2+5+56=4V=5+5+2+2+5+56=4. We output V=4

For Solution

Click Here!

Leave a Comment

Your email address will not be published.