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

×

GOODS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Jatin Gupta
Tester: Aanya Jindal
Editorialist: Naman Goyal

DIFFICULTY:

EASY

PREQUISITES

Sorting

PROBLEM:

In problem statement, it is given that there are n(even) number of people and we have to do pairing of them in such a manner that the sum of the numbers assigned to them should be greater than k.

QUICK EXPLANATION:

After sorting the laddus, we take last and first element. If they form a valid pair, then we take the next minimum and next maximum laddus. Else, we advance the minimum and add 1 to the unsatisfied number of people.(As the minimum cant form valid pair with any other remaining person).

EXPLANATION:

We have to minimise the number of people left who can not reach the given amount(k).

We see how we can use the greedy strategy to solve the given problem.

If the sum of laddus of 2 people is greater than k, then it does not matter how much greater than k they have.

So we try to pair the person with maximum laddus with the person having minimum laddus. If they are not able to form a valid pair, then the person having minimum laddus cannot form a valid pair with anyone else. So, we add that person to the list of people who can't be in any pair.

(Let’s say we use an array as our data structure, then sorting gives an ordered arrangement of the elements in ascending manner.)

To minimize the number of people left we need to take the minimum and maximum amount of the array and then check whether their sum is greater than k or not.

If yes, then move on to the next minimum and maximum number and repeat the process until we reach the point where minimum and maximum become same or minimum become greater than maximum.

If no, then check for the next minimum number keeping the maximum number same and repeat the checking process until we reach the point where minimum and maximum become same or minimum become greater than maximum.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

asked 24 Apr '18, 13:05

jatin_cpp's gravatar image

5★jatin_cpp
41
accept rate: 0%

edited 26 Apr '18, 16:41

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
×3,820
×1,024
×801
×10

question asked: 24 Apr '18, 13:05

question was seen: 187 times

last updated: 26 Apr '18, 16:41