[Solution] Too Mean solution codechef

Too Mean solution codechef – You are given an array A of length N.

[Solution] Too Mean solution codechef

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

Each element Ai (1≤i≤N) belongs to exactly one subsequence.
The mean of the mean of subsequences is maximised.
Formally, let S1,S2,…,SK denote K subsequences of array A such that each element Ai (1≤i≤N) belongs to exactly one subsequence Sj (1≤j≤K).
Let Xj (1≤j≤K) denote the mean of the elements of subsequence Sj. You need to maximise the value ∑Kj=1XjK.

Print the maximum value. The answer is considered correct if the relative error is less than 10−6.

[Solution] Too Mean solution codechef

First line will contain T, number of test cases. Then the test cases follow.
First line of each test case consists of a single integer N – denoting the length of array A.
Second line of each test case consists of N space-separated integers A1,A2,…,AN – denoting the array A.

Output Format

For each test case, output in a single line, the maximum possible mean of mean of subsequences. The answer is considered correct if the relative error is less than 10−6.

[Solution] Too Mean solution codechef

  • 1≤T≤1000
  • 2≤N≤105
  • 1≤Ai≤106

Sum of N over all test cases does not exceed 3⋅105.

Sample Input 1

3
2
10 20
3
1 2 3
5
50 50 50 50 50

Sample Output 1

15
2.25
50

Too Mean solution Explanation

Test Case 1: We can partition the array in 2 ways – ({10},{20}) or ({10,20}). In both cases, mean of mean of subsequences comes out to be 15.

Test Case 2: The optimal partition is ({1,2},{3}).

Mean of first subsequence =1+22=1.5.
Mean of second subsequence =31=3.
Thus, mean of mean of subsequences is 1.5+32=4.52=2.25.

Test Case 3: Any partition will yield the mean of mean of subsequences as 50.

For Solution

Click here

Leave a Comment