PROBLEM LINK:
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.