PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Aditya Dimri
Tester: Encho Mishinev
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
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
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>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;
}
Tester’s Solution
Click to view
#include
#include
using namespace std;
int t;
int n;
int MIN(int a,int b)
{
if (a < b)
return a;
else
return b;
}
int MAX(int a,int b)
{
if (a > b)
return a;
else
return b;
}
int main()
{
int i;
int test;
scanf("%d",&t);
for (test=1;test<=t;test++)
{
scanf("%d",&n);
int pos = 0;
int neg = 0;
for (i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
if (a < 0)
neg++;
else
pos++;
}
if (neg == 0)
printf("%d %d\n",pos,pos);
else if (pos == 0)
printf("%d %d\n",neg,neg);
else
printf("%d %d\n", MAX(neg,pos), MIN(neg,pos));
}
return 0;
}
Editorialist’s Solution
Click to view
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
int a = 0, b = 0;
for(int i = 0; i< n; i++){
long c = nl();
if(c<0)a++;
else b++;
}
if(Math.max(a, b)==n)pn(n+" " +n);
else pn(Math.max(a, b)+" "+Math.min(a,b));
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e3+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 