TOOMEAN Editoriale

editorial
, ,
1

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

2

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;
}
3

Why partitioning only in 2 parts gives the optimal answer?

4

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