BUY1GET1 - Editorial

pragrame · February 12, 2013, 6:20pm

Problem Link:

Practice

Contest

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

cprgdaksh · February 13, 2013, 7:34pm

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;
}

THANKS IN ADVANCE
EAGERLY WATING FOR REPLY

anton_lunyov · February 13, 2013, 7:45pm

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++)

abhashksingh · February 15, 2013, 11:39am

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

whats wrong with this solution??

polisettyvarma · February 16, 2013, 11:05am

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

what’s the problem with this logic???

vineetpaliwal · February 16, 2013, 11:11am

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

anuj_mahajan · February 16, 2013, 10:15pm

someone please help me out.
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;
}

Thanks in advance.

pragrame · February 17, 2013, 3:48am

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

ritu2510 · February 17, 2013, 4:19am

whats the problem with the following code???

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

bugkiller · February 17, 2013, 2:47pm

@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

ritu2510 · February 17, 2013, 3:38pm

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

abhashksingh · February 18, 2013, 1:30pm

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

anton_lunyov · February 18, 2013, 4:20pm

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

anton_lunyov · February 18, 2013, 4:34pm

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

anton_lunyov · February 18, 2013, 4:36pm

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

rajat152 · April 19, 2013, 1:37am

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

gopi1857 · April 2, 2014, 2:15pm

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

affiszerv · April 22, 2014, 10:32pm

yeah I was getting WA, then simply added

abc = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

…
if c in abc:
…

And got AC

soumya_13106 · June 26, 2014, 11:26am

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

Please me the problem in the solution.
Thanks in advance!

pratku123 · June 26, 2014, 2:33pm

@soumya_13106, you are supposed to count the number of times each character occurs in the string. Now in your solution you are not counting the frequency of the character, you are just storing if they occur or not. Suppose ‘A’ occurs 5 times the ans will be incremented by 5/2+5%2; do this for all the characters. Store their frequency in the array val[](instead of storing 1), and then increment the answer for all the non- zero values of val[].
try it first and if still there is a problem, I have corrected your solution: http://www.codechef.com/viewsolution/4144576