CHNUM - EDITORIAL

editorial
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Aditya Dimri
Tester: Encho Mishinev
Editorialist: Taranpreet Singh

DIFFICULTY:

PREREQUISITES:

Basic Math.

PROBLEM:

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.

QUICK EXPLANATION

  • 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.

EXPLANATION

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

Time complexity is O(N) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s Solution

Click to view

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen(“inp5.in”,“r”,stdin);
//freopen(“op5.out”,“w”,stdout);
int t;
cin>>t;
while(t–)
{
long long int n;
cin>>n;
//long long int arr[n];
//memset(arr,0,sizeof(arr));
long long int pos=0;
long long int neg=0;
for(long long int i=0;i<n;i++)
{
long long int val;
//cin>>arr[i];
cin>>val;
if(val>0)
pos++;
else
neg++;
}
if(pos==0||neg==0)
cout<<max(pos,neg)<<" “<<max(pos,neg)<<”\n";
else
cout<<max(pos,neg)<<" “<<min(pos,neg)<<”\n";
}
return 0;
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile: