Given an array A of size N, Divide it into K non-empty groups and for each group, Take the summation of scores in a group. The final score is the sum of squares of scores in each group. We need to find the minimum and maximum size of groups which maximize the score.
Note that A does not contain zero.
- Only the absolute values of the sum of groups matter. Higher the absolute value of a group, the better. So, It makes sense not to put both positive and negative numbers in the same group.
- Since (x+y)^2 = x^2+y^2+2*x*y > x^2+y^2 when both x and y are either positive or negative, we should put numbers with same sign in the same group.
- So, We put all positive numbers in one group, negative numbers in other group and print group sizes.
First of all, let us consider two elements x and y to be present in the array A. We shall analyze whether which way gives a better score, putting both in the same group or different groups.
While putting both in the same groups, Score of that group is (x+y)^2 = x^2+y^2+2*x*y, but if we put both in separate groups, the score is x^2+y^2. Both Scores differ by 2*x*y.
If x*y > 0, we should put both elements in the same group, which happens when both x and y both are either negative or positive.
Otherwise, we have x*y < 0 when one element is positive and other is negative. We put them in different groups.
So, we can conclude that we need to put all positive elements in one group and all negative numbers in another group. We can just find out the number of positive and negative elements present in the array A and print minimum and maximum group sizes. If one of the group is empty, we have only one group and we print its size as both minimum and maximum.
Problem to try
Given an array A of size N, divide all elements into K non-empty groups such that sum of sz_i*sum_i is maximized where sz_i is the size of the ith group and sum_i is the sum of the ith group. (This is a past contest problem which I can’t find now xD).
Time complexity is O(N) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Click to view
using namespace std;
long long int n;
//long long int arr[n];
long long int pos=0;
long long int neg=0;
for(long long int i=0;i<n;i++)
long long int val;
Feel free to Share your approach, If it differs. Suggestions are always welcomed.