PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Jeevan Jyot Singh
Tester : Takuki Kurokawa
Editorialist: Aman Dwivedi
DIFFICULTY:
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.
Now let’s move one element from set Q to set P. Let’s call it Sum_2
Now if our claim is true, it means Sum_1 > Sum_2
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
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;
}
