PROBLEM LINK:
Practice
Contest
Author: Sameer Gulati
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov
DIFFICULTY:
simple
PREREQUISITES:
None
PROBLEM:
You are given set of integers. You have to split it into subsets in such way that \sum\limits_{subsets}|subset_i| \times\left(\sum\limits_{j\in subset_i}a_j\right) is maximized.
EXPLANATION:
Since we want to maximize multiplier of positive elements, they all should be in the same subset. Also we can take with them some largest of negative elements.
Since we want to minimize the multiplier of negative elements, each of remaining negative elements will be in the set containing only this element (i.e. single element sets).
Thus we bruteforce the number of negative elements which will be in the set with positive ones and choose the best possible sum among all this variants.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be updated soon.
Tester’s solution will be updated soon.
Editorialist’s solution will be updated soon.
RELATED PROBLEMS:
See this test case:
n=8
-5 -3 -2 0 0 2 8 12
Answer = 114 . But as most people have done their answer would come 112 and still would pass.
3 Likes
could u explain how it is 114?
@coddic_13
In first step, take first element. In second step consider rest of the elements.
-5 + (-3 + -2 + 0 + 0 + 2 + 8 + 12) * 7 = 114.
Very weak test cases.
1
5
-50 -100 -60 130 120
correct answer is 460. but many AC solution gives 440.
I am iterating over all the possible subset of dishes having negative happiness value.
but this leads to exponential order. here is my code.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n;
cin >> t;
while (t–)
{
cin >> n;
vector v;
int sum = 0, size = 0, x, ans = 0;
for (int i = 0; i < n; i++)
{
cin >> x;
ans += x;
if (x < 0)
{
v.push_back(x);
}
else
{
sum += x;
size++;
}
}
ans *= n;
n = v.size();
int temp1, sz, temp2;
for (int i = 0; i < (1<< n); i++)
{
temp1 = 0, sz = 0, temp2 = 0;
for (int j = 0; j < n; j++)
{
if (((1l<< j) & i))
{
temp1 += v[j];
sz++;
}
else
{
temp2 += v[j];
}
}
ans = max(ans, (sum + temp1) * (size + sz) + temp2);
}
cout << ans << “\n”;
}
return 0;
}
can someone provide an optimal approach.
thanks in advance.