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

×

NEO01 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sameer Gulati
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov

DIFFICULTY:

simple

PREREQUISITES:

None

PROBLEM:

You are given set of integers. You have to split it into subsets in such way that $\sum\limits_{subsets}|subset_i| \times\left(\sum\limits_{j\in subset_i}a_j\right)$ is maximized.

EXPLANATION:

Since we want to maximize multiplier of positive elements, they all should be in the same subset. Also we can take with them some largest of negative elements.

Since we want to minimize the multiplier of negative elements, each of remaining negative elements will be in the set containing only this element (i.e. single element sets).

Thus we bruteforce the number of negative elements which will be in the set with positive ones and choose the best possible sum among all this variants.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be updated soon.
Tester's solution will be updated soon.
Editorialist's solution will be updated soon.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 12 Jun, 10:02

melfice's gravatar image

3★melfice
111
accept rate: 0%

edited 12 Jul, 00:23

admin's gravatar image

0★admin ♦♦
15.5k347484505

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:

×11,354
×2,591
×144
×4

question asked: 12 Jun, 10:02

question was seen: 197 times

last updated: 12 Jul, 00:23