CHNUM - EDITORIAL

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*;
            cin>>val;
            if(val>0)
                pos++;
            else
                neg++;
        }
        if(pos==0||neg==0)
            cout<<max(pos,neg)<<" "<<max(pos,neg)<<"
";
        else
            cout<<max(pos,neg)<<" "<<min(pos,neg)<<"
";
    }
    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
",pos,pos);
        else if (pos == 0)
            printf("%d %d
",neg,neg);
        else
            printf("%d %d
", 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. :slight_smile:

Hi Setter’s solution is truncated. Also, most of the code is not commented. There is no code alignment. Is there anyway we can do this better and improve code quality ?

This is the first time I am trying to submit a code. I have literally copied the code from “Tester’s solution” and did some beautification. It doesn’t work. It fails when I submit.

There is no option for me to debug. No hints are provided. Later came to know that it was failing because of missing new line at end the end of my program.

Thank you,
Murali