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.
@abhashksingh : The ascii value of ‘a’ is 97 and not 71. Just think ‘A’ is 65 so next 25 values will be for upper case letters , so how can lower case letters start at 71 . Thats the bug in your code .
@ritu2510 >> You are not supposed to print the “enter the number of test cases” thing here in the programs. There are testdata and your program is supposed to take input from standard input and give output on the standard output. It need not be “user friendly” in the output, it should just give correct output for each corresponding input.
UPD.
Moreover, you need not store all the input in an array and then display output at once. You should take an input and do the calculations and print the output and then take the next input and proceed in the same manner.
See, I modified your code: removed the “enter the number of test cases” thing and removed the array a[] into just a string a and it got Accepted. CodeChef: Practical coding for everyone
My code runs within time produces desired results uses the obvious login but still i am getting wrong answer!! please could someone help me with my following code:- CodeChef: Practical coding for everyone
I am not sure in which test case it is failing… ? It worked for all the inputs provided in the Question. Can someone please point out the error in the logic.