MEANMAX - Editorial

Author: Jeevan Jyot Singh
Tester : Takuki Kurokawa
Editorialist: Aman Dwivedi

Simple

PREREQUISITES:

Maths, Observation

PROBLEM:

You have an array A of length N. You want to divide the array A into two non-empty subsets P and Q such that the value of mean(P)+mean(Q) is as large as possible. (Note that each A_i must belong to either subset P or subset Q).

Find this maximum value of mean(P)+mean(Q).

EXPLANATION:

Let’s put the maximum element of an array in one of the sets say P and the remaining elements in another set Q.

We claim that this division will result in the maximization of mean(P)+mean(Q). Let’s prove:

Suppose we do the first division as above which means set P contains a_1 and the rest of the other elements are in the set Q. Let’s say this value is Sum_1.

Sum_1 = a1+\frac{a2+a3+.....+a_n}{n-1}
Sum_1 = \frac{a1*(n-1) + (a_2+a_3+.....+a_n)}{n-1}

Now let’s move one element from set Q to set P. Let’s call it Sum_2

Sum_2 = \frac{a_1+a_2}{2} + \frac{a_3+a_4+......+a_n}{n-2}
Sum_2 = \frac{(n-2)(a_1+a_2) +2(a3+a_4+.....+a_n)}{2(n-2)}

Now if our claim is true, it means Sum_1 > Sum_2

\frac{a1(n-1) + (a_2+a_3+.....+a_n)}{n-1} > \frac{(n-2)(a_1+a_2) +2(a3+a_4+.....+a_n)}{2(n-2)}
2a_1(n-1)(n-2)+2(n-2)(a_2+a_3+\dots+a_n) > (n-1)(n-2)(a_1+a_2)+2(n-1)(a_3+a_4+\dots+a_n)
a_1(n-1)(n-2)+2(n-2)a_2-(n-1)(n-2)a_2 > 2(a_3+a_4+\dots+a_n)
a_1(n-1)(n-2)+a_2(n-2)(2-n+1) > 2(a_3+a_4+\dots+a_n)

Now as we have said earlier a_1 is the maximum element of the array let’s replace it with the max and all other elements with max-1 since all other elements will be less than max

max(n-1)(n-2) - (max-1)(n-2)(n-3)> 2(n-2)(max-1)
((n-1)-(n-3)) max + n > 2max+1
2max+n>2max+1
n>1

It means when n>1 then the division which puts the maximum element of an array in one of the sets say P and the remaining elements in another set Q maximizes the value.

When all the elements are equal to max you can see all the divisions will work.

TIME COMPLEXITY:

O(N) per test case

SOLUTIONS:

Author's Solution
#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

void solve()
{
int n; cin >> n;
int sum = 0, mx = 0;
for(int i = 0; i < n; i++)
{
int x; cin >> x;
mx = max(mx, x);
sum += x;
}
cout << 1.0 * mx + 1.0 * (sum - mx) / (n - 1) << "\n";
}

int32_t main()
{
IOS;
cout << fixed << setprecision(9);
int T; cin >> T;
for(int tc = 1; tc <= T; tc++)
{
solve();
}
return 0;
}

Tester's Solution
// tester solution for editorial. please remove this comment section.
#include <bits/stdc++.h>
using namespace std;

int main() {
cout << fixed << setprecision(8);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
int mx = 0;
for (int i = 0; i < n; i++) {
mx = max(mx, a[i]);
}
double mean_p = mx;
double mean_q = 1.0 * (sum - mx) / (n - 1);
cout << mean_p + mean_q << '\n';
}
return 0;
}

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

void solve()
{
int n;
cin>>n;

int mx = -1;
int sum = 0;

for(int i=0;i<n;i++)
{
int x;
cin>>x;

mx = max(x,mx);
sum+=x;
}

double ans = (double)(sum-mx)/(double)(n-1);
ans += (double)(mx);

cout<<fixed<<setprecision(10)<<ans<<"\n";
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}


2 Likes

This problem was the exact copy of : Problem - A - Codeforces

12 Likes

You didn’t care for the precision issues that’s why

1 Like

Thanks a lot

Can we sort the array and put the elements alternatively in both arrays?

for example if arr=[5,4,3,2,1]
then p=[5,3,1] q=[4,2]
will it not give the required ans??

I have tried this approach and it gave me WA
my solution 1
my solution 2
my solution 3
my solution 4

1 Like

Accepted in Java

import java.util.*;
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
long[] arr = new long[n];
for(int i=0;i<n;++i)
arr[i] = sc.nextLong();
Arrays.sort(arr);
double ans = 0;
long sum = 0;
for(int i=0;i<n-1;++i)
sum+=arr[i];
ans = (double)sum/((double)n-1);
ans+=(double)arr[n-1];
System.out.println(String.format("%6f",ans));
}
}
}


Because, when you take mean of a set of elements then, mean of the set is always less than or equal to the maximum element of that set. There are 2 cases:

1.Mean will be equal to the maximum element of the set when all the elements of the set are equal.
example: a=[4,4,4,4,4], mean(a)=(4*5)/5 or 20/5
mean(a)=4
here, mean(a)=max(a)=4

2.Mean will be less than the maximum element of the set when all the elements of the set are not equal.
p=[5,3,1], mean(p)=(5+3+1)/3 or 9/3
mean(p)=3
here, mean(p) < max(p)
i.e. 3< 5

Therefore, taking in mind the above two points, we put the maximum element of the array in one set, so that the mean of one set is always the maximum element of the set and in other set we put all the other elements of the array.

Hence, our answer is always greater than the maximum element of the array.
If you put the maximum element of the array with other elements of the array, mean of that set is always less than or equal to the maximum element of the array.
eg. a=[2,5,9,6]
make 2 set p and q. p contains the maximum elements with the other one while q contains the rest of the elements.
p=[9,5]
mean(p)=7, which is less than 9.
So, why should we put the maximum elements with other elements?

2 Likes

Mean of set which contains elements (6,7,5) is 6 not 9.

1 Like

Thank you very much for the explanation

Can anyone help with counter example for this code ? Solution: 56894888 | CodeChef
I am following same logic but might have missed something/made some logical error

This is your modified code and it is accepted. The only change that i made in it is that i add setprecision function for precision of floating number. The same mistake i also did in the contest.

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

int main() {
int t,n,a[1002];
cin>>t;
while(t–){
cin>>n;
int sum,max;
sum=0;
max=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
if(max<a[i])
max=a[i];
}
n–;
float ans=(sum-max);
ans=ans/n;
ans=ans+max;
cout<<fixed<<setprecision(6)<<ans<<"\n";
}
return 0;
}

1 Like

With max < a[i] it’ll always be set to 0!

No it wouldn’t mate. It would be changed by any first positive number and then will keep it updated to max one. Can you revert on why you think it will keep it as 0?

Thanks man. But still never thought I would have to add precision

1 Like

This was my first codechef contest, pardon my stupid usage of huge arrays(i don’t fully know linked lists yet), but where did it go wrong?
#include <stdio.h>

int main(void) {
int t=0;
int a[1000];
int b[1000];

int i=0;
int n;
float mean=0;

scanf("%d",&t);
for(t;t>0;t--){
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(i=0;i<n;i++){

b[i]=a[i];
}

for(i=0;i<n;i++){
if(a[0]< a[i]){
a[0]=a[i];
}

}
for(i=0;i<n;i++){
mean=mean+b[i];
}mean=mean-a[0];
mean=mean/(n-1);
mean=a[0]+mean;
printf("%f",mean);

}
return 0;


}

@cherry0697 I was upsolving this problem and by my intutiton I reached to this conclusion that the answer is after the sorting the array we need to print the sum of mean of first n-1 elements and the last element(the max element)

Now since it dealt with precision issues, in my first attempt I wrote this expression
ans = (a_1 + a_2 + … + a_{n-1})/(n-1) + a_n
ans= ((a_1 + a_2 + … + a_{n-1})+ (n-1)a_n)/(n-1)

I tried this final expression for ans but it gave WA and then I computed for every prefix taking individual mean and adding them and it passed.