PROBLEM LINK:
Author: Anudeep Nekkanti
Tester: Minako Kojima
Editorialist: Lalit Kundu
DIFFICULTY:
EASY
PRE-REQUISITES:
Sorting, Greedy
PROBLEM:
You have to buy N items of cost A1, A2 … AN. For every two items you buy, they give you two items for free. However, items can be of varying price, they always charge for 2 most costly items and give other 2 as free. For example, if the items cost 1, 1, 2, 2, then you have to pay 4 and take all 4 items.
Find minimum price in which you can buy all items?
QUICK EXPLANATION:
Sort the array A and greedily start choosing from largest elements.
EXPLANATION:
Claim 1:
We should pick the most costliest and second most costliest items in a single bill.
Proof:
Assume x be the most costliest item and y be the second most costliest item. Assume x and y are in different bags. There can be two cases.
- The bag containing x, has only one element.
We can add y in the same bill too because we are anyway paying for both, so why two separated bills instead of one. - The bag containing x, has more than element. Assume z be the second most costliest item in bag containing x.
Now we can simply swap y and z. So we will end up x and y being in same bag. Also due to this swapping, there is no change in cost because we were anyway paying for both x and y before.
After picking the most costliest items in a single bill, we should try to pick the third and fourth most costliest items also in the same bag to get most benefit of buy 2, get 2 free scheme. As the third and fourth items will be free.
We can even formally prove this part similar to swapping item used in previous claim.
This concludes the mathematical proof required.
Now that we have chosen one group we’ll choose further groups from remaining array A.
This is the design of our greedy algorithm. We sort the array A first and then start choosing groups of 4 in decreasing order of array A. This will ensure that we make minimum sum.
Pseudo code:
A = input
sort(A)
reverse(A)
ans = 0
for i=0 to N-1:
//count in answer the index 0,1,4,5,8,9...
if i%4 < 2:
ans += A[i]
print ans
Complexity: O(N log N) due to sorting.