# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Utkarsh Gupta

Tester: Jakub Safin, Satyam

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2254

# PREREQUISITES:

None

# PROBLEM:

You are given an array A of length N.

You have to partition the elements of the array into some subsequences such that:

- Each element A_i (1 \le i \le N) belongs to
**exactly one**subsequence. - The mean of the mean of subsequences is
**maximised**.

Formally, let S_1, S_2, \dots, S_K denote K subsequences of array A such that each element A_i (1 \le i \le N) belongs to exactly one subsequence S_j (1 \le j \le K).

Let X_j (1 \le j \le K) denote the mean of the elements of subsequence S_j. You need to maximise the value \frac{\sum_{j=1}^K X_j}{K}.

Print the maximum value. The answer is considered correct if the relative error is less than 10^{-6}.

# EXPLANATION:

Sort the array A in non-increasing order.

For a fixed n_1 \leq n_2 \leq ... \leq n_k, the sizes of the blocks in the partition, It is optimal to partition it into

Now fix some k, Consider n_1 \leq n_2 \leq ... \leq n_k, the sequence of partition sizes corresponding to optimum. If there are multiple such sequences, choose one with minimum n_1. Let m_1, m_2, ... m_k be the means of corresponding partitions.

Assume n_1 > 1, We have

If we move A_{n_1} to second block, the new mean of first block is

which is clearly \geq m1 as removing the minimum in a sequence increases it’s mean and the new mean of second block is

Since A is in non-increasing order, A_{n1} >= A_{n_1 + i} for all 1 <= i <= n_2 so m_{2'} is clearly \geq m_2 because A_{n_1} >= m_2 so by shifting A_{n_1} to second block may give a better partition but not worse.

But we chose the partition with minimal n_1. A contradiction. So, n_1 = 1.

Using induction, we can prove that n_i = 1 for all i < k and n_k = n - k + 1 is the optimal way to partition.

Thus we can choose values of k from 1 to N and calculate the corresponding mean, the maximum of which would be our answer.

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester1’s Solution

Tester2’s Solution