# Problem Link:

# Difficulty:

CAKEWALK

# Pre-requisites:

Ad-hoc

# Problem:

You are given a set of jewels of different colors that you need to purchase. Buying a jewel of color **k** makes you eligible to get another jewel of color **k** for free, by availing of the Buy1-Get1 offer. All jewels, irrespective of color, cost 1. Find the minimum cost you pay by using Buy1-Get1.

# Explanation:

Consider a frequency array where each element stores how many jewels of that particular color are there. There are only 52 colors (from the constraint that each color is denoted by a case-sensitive latin character).

Now, the answer = sum ceil(f[i]/2).

Lets argue this using a necessary-and-sufficient-condition argument.

Q. Why do we need at least sum ceil(f[i]/2)?

A. To acquire the jewels of color ‘i’, lets say we pay ‘k’ amount of money. So the rest has been got for free, i.e. f[i] - k times we have used Buy1Get1 for this color. But we can use only k times the Buy1-Get1 offer (on this color). So k >= f[i]-k, which gives us that the minimum required amount to be paid for acquiring all f[i] jewels of color i is at least f[i]/2.

Hence, to acquire all jewels, we need at least sum ceil(f[i]/2) money.

Q. Why is sum ceil(f[i]/2) sufficient?

A. It is in fact true, that ceil(f[i]/2) is sufficient to acquire all f[i] jewels of color i. For this, lets arrange the f[i] jewels in a row, and then, for each one we buy, the next one we take for free. In this way, we are saving the cost of every alternate jewel. Hence, this takes ceil(f[i]/2) amount of money. The total is thus, overall sum ceil(f[i]/2).

Time Complexity: O(T * |S|). |S| per test-case to update the frequency array.

# Author’s Solution:

Can be found here

# Tester’s Solution:

Can be found here