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