Practice

Contest

CAKEWALK

# 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

3 Likes

PLEASE TELL ME THE PROBLEM IN THE FOLLOWING CODE

``````#include <stdio.h>
int main()
{
int t, i, len, co=0, h, y, a=0, cost[100], tem=0;
char s[200], alp, x[]="qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM";
scanf("%d", &t);
for(i=1; i<=t; i++){
co=0;
scanf("%s", s);
//printf("%c", s[0]);
len=strlen(s);
for(h=0; h<=51; h++){
alp=x[h];
a=0;
for(y=0; y<len; y++){
if(s[y]==alp){
a++;
}
}
if(a % 2 == 1){
a=(a/2)+1;
}
else{
a=a/2;
}
co=co+a;
}
cost[tem]=co;
tem++;

}
for(tem=0; tem<t; tem++){
printf("%d\n", cost[tem]);
}
return 0;
}
``````

The only mistake is the small size of the array `s`.
Instead of 200 there should be 201. Simply fixing this gets AC:
http://www.codechef.com/viewsolution/1835761
(I should also add `string.h` library to get this compiled at C++)

http://www.codechef.com/viewsolution/1808761

whats wrong with this solution??

http://www.codechef.com/viewsolution/1835815

what’s the problem with this logic???

@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 .

I am getting wrong answer for this solution

``````#include<stdio.h>
#include<string.h>

int main()
{
int test = 0,hash_jew[150] = {0} ,count = 0;
char c = 0;
scanf("%d",&test);
while(test--)
{
fflush(stdin);
while(1)
{
scanf("%c",&c);
if(c == '\n')
break;
hash_jew[c] = hash_jew[c]^1;
count = count + hash_jew[c];
}
printf("%d\n",count);
memset(hash_jew,0,sizeof(hash_jew));
count = 0;
}
return 0;
}
``````

When I used `scanf("%s",c)` as i/o then it got accepted.
Please tell me the difference between these two.

Accepted code:

``````#include<stdio.h>
#include<string.h>

int main()
{
int test = 0, hash_jew[150] = {0}, count = 0, l, i;
char c[1000];
scanf("%d\n",&test);
while(test--)
{
scanf("%s",c);
l=strlen(c);
for(i=0;i<l;i++)
{
hash_jew[c[i]] = hash_jew[c[i]]^1;
count = count + hash_jew[c[i]];
}
printf("%d\n",count);
memset(hash_jew,0,sizeof(int)*150);
count = 0;
}
return 0;
}
``````

If ‘A’ … ‘Z’ is 0 to 25, then it makes sense to have ‘a’ as 26 etc. 97-71 = 26, so it seems fine.

1 Like

whats the problem with the following code???

http://www.codechef.com/viewsolution/1844213

@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. http://www.codechef.com/viewsolution/1844773

ohkay…got it…removing the “enter the number of test cases” is helping…thanx!!
and yeah… storing it in an array was not required.

@vineetpaliwal : I made sure that every letter gets a unique index.(uncomment cout on line 42)If possible may I know the test cases where my code fails.

The reason is that input files were generated under Windows and has character `'\r'` before each newline.
It is explained in the FAQ:

Refer to my comment to this answer.

Also just a suggestion - you can output the answer of each test case before input next test case. It should simplify your code

The reason is that input files contains hidden `'\r'` characters in the end of each line. Refer to this:

http://www.codechef.com/viewsolution/2058133
what is wrong with my solution?

Iam Getting wrong answer ,some might test cases might be missing pls suggest some typical test cases…

yeah I was getting WA, then simply added

``````abc = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
``````

if c in abc:

And got AC

http://www.codechef.com/viewsolution/4144022

Please me the problem in the solution.