TOOMEAN Editoriale

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

[A_1, .... A_{n_1}], [A_{n_1 + 1} ... A_{n_1 + n_2}]....

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

m_1 = \frac{(A_1 + ... + A_{n_1})}{n_1} \\ m_2 = \frac{(A_{n_1 + 1} + ... A_{n_1 + n_2})}{n_2}

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

m_{1'} = \frac{(A_1 + .... A_{n_1 - 1})}{(n_1 - 1)}

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

m_{2'} = \frac{(A_{n_1} + A_{n_1 + 1} + ... A_{n_1 + n_2})}{(n_2 + 1)}

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

In the explanation, they sort it in descending order but in their codes, they sorted it in ascending order, so here’s my code which follows their explanation.


#include <bits/stdc++.h>
using namespace std;

// #define ll long long int
#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define mod 1000000007

int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("input.txt",  "r",  stdin);
	freopen("output.txt", "w", stdout);
	#endif


	int t = 1;
	cin >> t;
	cin>>ws;
	while (t--) 
	{
		int n;
		cin>>n;
		double arr[n];
		double sum = 0;
		for(int i = 0; i<n; i++){
			cin>>arr[i];
		}
		sort(arr, arr+n, greater<int>());
		for(int i = 0; i<n; i++){
		    sum += arr[i];
		    arr[i] = sum;
		}
		double ans = sum/n;
		for(int i = 1; i<n; i++){
		    ans = max(ans, (arr[i-1] + (sum - arr[i-1])/(n-i))/(i+1));
		}
		cout<<fixed<<setprecision(6)<<ans<<endl;
	}
	return 0;
}

Why partitioning only in 2 parts gives the optimal answer?

Can someone Explain me With example
it’s very Hard to understand : (