BUY1GET1 - Editorial

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

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

THANKS IN ADVANCE
EAGERLY WATING FOR REPLY

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 .

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.

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

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…

Can someone help identify bugs in my code? Or point me towards a few helpful test cases?

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

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

This is getting a WA respose.


	use POSIX;
	$,=",";
	my $T=<>;
	chomp($T);
	while($T--){
		my $str=<>;
		chomp($str);
		my $ans=0;
		my %charCount;
    

			for(my $i=0;$i<length($str);$i++){
				$charCount{substr($str,$i,1)}++;
			}
			for(values %charCount){
				$ans+=ceil($_/2);
			}
		print $ans .  "\n";
	}

Can someone help with this.

#include<stdio.h>
#include<string.h>
int main()
{
int t,j,i,count;
char a[201];
scanf("%d",&t);
while(t–)
{
count = 0;
scanf("%s",a);
for(i=0;i<strlen(a)-1;i++)
{
if(a[i]!=’’)
{
for(j=i+1;j<strlen(a);j++)
{
if(a[i]==a[j])
{
a[i]=’
’;
a[j]=’*’;
count++;
}
}
}
}
printf("%d\n",strlen(a)-count);
}
return 0;
}

what is wrong with this solutions works fine on my pc but gives wrong answer here. please help.

Why i’m getting wrong answer?
My code is
#include<stdio.h>
int check(int [],char);
int main()
{
int T,i,A[205]={0},cnt=0,x;
char ch[205];
scanf("%d",&T);
while(T–)
{ A[0]=-1;
cnt=0;
scanf("%s",ch);
for(i=0;ch[i]!=’\0’;i++)
{ x=check(A,ch[i]);
if(x)
{
cnt++;
}

        }
        for(i=0;A[i]!=-1;i++)
        {
            if(A[i]!=0)
            cnt++;
        }
        printf("%d",cnt);
}

return 0;
}

int check(int A[],char c)
{
int x,i;
for(i=0;A[i]!=-1;i++)
{
if(A[i]==c)
{
A[i]=0;
return 1;
}
}
A[i]=c;
A[i+1]=-1;
return 0;

}

I have tried my best to debug this code but can’t find the test cases am failing in , please correct my mistakes , it’s not very lengthy :

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

Can you tell me why this soln is wrong ?
It’s working perfectly fine in my m/c for all sorts of i/p
https://www.codechef.com/viewsolution/8339530

can u please tell my mistake in this code…
https://www.codechef.com/viewsolution/8534920

use someother value instead of “0” when u are marking, your loop is ending when its reaching any index where a[i]==0(0==NULL). -1 will work.

I have implemented the following solution. https://www.codechef.com/viewsolution/8932461

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.