NOIP '21 P3 - Variance

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

You are given a sequence of nondecreasing positive integers 1 \le a_1 \le a_2 \le \dots \le a_n.

At each step, you can perform the following operation: Choose any positive integer 1 < i < n, change a_i to a_{i-1}+a_{i+1}-a_i.

Determine the minimum variance of the sequence a after performing any number of operations.

The variance is the average of the squared differences between numbers and their mean value. Formally, variance is D = \frac 1 n \sum_{i=1}^n (a_i-\overline a)^2 where \overline a = \frac 1 n \sum_{i=1}^n a_i.

Input Specification

The first line contains a positive integer n. It is guaranteed that n \le 10^4.

The second line contains n positive integers where the i-th number represents the value of a_i. The data guarantee that 1 \le a_1 \le a_2 \le \dots \le a_n.

Output Specification

Output a single nonnegative integer representing n^2 times the minimum variance you determine.

Sample Input 1

4
1 2 4 6

Sample Output 1

52

Sample 1 Explanation

For (a_1, a_2, a_3, a_4) = (1, 2, 4, 6), after the first operation, we can get (1, 3, 4, 6). After the second operation, we can get (1, 3, 5, 6). After that we cannot get any new sequence.

For (a_1, a_2, a_3, a_4) = (1, 2, 4, 6), the mean is \frac{13}{4}, the variance is \frac{1}{4}((1-\frac{13}{4})^2+(2-\frac{13}{4})^2+(4-\frac{13}{4})^2+(6-\frac{13}{4})^2)=\frac{59}{16}.

For (a_1, a_2, a_3, a_4) = (1, 3, 4, 6), the mean is \frac{7}{2}, the variance is \frac{1}{4}((1-\frac{7}{2})^2+(3-\frac{7}{2})^2+(4-\frac{7}{2})^2+(6-\frac{7}{2})^2)=\frac{13}{4}.

For (a_1, a_2, a_3, a_4) = (1, 3, 5, 6), the mean is \frac{15}{4}, the variance is \frac{1}{4}((1-\frac{15}{4})^2+(3-\frac{15}{4})^2+(5-\frac{15}{4})^2+(6-\frac{15}{4})^2)=\frac{59}{16}.

Additional Samples

Additional samples can be found here.

Constraints

Test cases n \le a_i \le
1\sim 3 4 10
4\sim 5 10 40
6\sim 8 15 20
9\sim 12 20 300
13\sim 15 50 70
16\sim 18 100 40
19\sim 22 400 600
23\sim 25 10000 50

For all test cases, it is guaranteed that n \le 10\,000, a_i \le 600.


Comments

There are no comments at the moment.