You are not logged in. Please login at www.codechef.com to post your questions!

×

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

View Content

Tester's Solution

View Content

Editorialist's Solution

View Content

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

This question is marked "community wiki".

asked 13 Mar, 16:13

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 13 Mar, 19:21

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,688
×1,220
×724
×75
×5

question asked: 13 Mar, 16:13

question was seen: 833 times

last updated: 13 Mar, 19:21