PROBLEM LINK:Author: Anudeep Nekkanti DIFFICULTY:EASY PREREQUISITES:Sorting, Greedy PROBLEM:You have to buy N items of cost A_{1}, A_{2} ... A_{N}. For every two items you buy, they give you two items for free. However, items can be of varying price, they always charge for 2 most costly items and give other 2 as free. For example, if the items cost 1, 1, 2, 2, then you have to pay 4 and take all 4 items. QUICK EXPLANATION:Sort the array A and greedily start choosing from largest elements. EXPLANATION:Claim 1:We should pick the most costliest and second most costliest items in a single bill. Proof:Assume x be the most costliest item and y be the second most costliest item. Assume x and y are in different bags. There can be two cases. After picking the most costliest items in a single bill, we should try to pick the third and fourth most costliest items also in the same bag to get most benefit of buy 2, get 2 free scheme. As the third and fourth items will be free. This concludes the mathematical proof required. Now that we have chosen one group we'll choose further groups from remaining array A. This is the design of our greedy algorithm. We sort the array A first and then start choosing groups of 4 in decreasing order of array A. This will ensure that we make minimum sum. Pseudo code:
Complexity: O(N log N) due to sorting. SOLUTIONS:
This question is marked "community wiki".
asked 19 Jan '15, 01:10

my solution was giving wrong answer. i don't know why. anyone tell what is the mistake in it. include<stdio.h>int cmpfunc(const void a,const void b) { return((int)b(int)a); } int main() { int T,N,a[1010]={0},i,sum; scanf("%d",&T); while(T) { scanf("%d",&N); for(i=0;i<N;i++) scanf("%d",&a[i]); qsort(a,N,sizeof(int),cmpfunc); //for(i=0;i<N;i++) // printf("%d ",a[i]); sum=0; for(i=0;i<N;i=i+4) {
} answered 19 Jan '15, 01:31

my solution is giving wrong answer. please tell me what are mistake in this code??
answered 19 Jan '15, 01:55

my solution is giving wrong answer. please tell me what is mistake in this code??
answered 19 Jan '15, 03:27

Can any one explain where my code is wrong.thanks in advance include<stdio.h>include<stdlib.h>int cmp(const void a,const void b){ return ( (int)a  (int)b ); } int main(){ int t,n,i; scanf("%d",&t); while(t){ scanf("%d",&n); int cost[n]; for(i=0;i<n;i++) scanf("%d",&cost[i]);="" long="" sum="0;" if(n<="4){" qsort(cost,n,sizeof(int),cmp);="" sum="cost[n1]+cost[n2];}" else{="" qsort(cost,n,sizeof(int),cmp);="" *for(i="0;i<n;i++)" printf("%d="" ",cost[i]);*="" for(i="n1;i">=0;i=i4){ sum=sum + cost[i]+cost[i1]; } } printf("%ld\n",sum); } return 0; } answered 19 Jan '15, 10:19

Please tell why codechef is telling "wrong answer" to this solution. Answers to the given test cases are coming out right. ps:i used bubble sort. ill use merge later on. answered 19 Jan '15, 13:41

Can someone tell where I'm making a mistake? I checked for the common single input mistake, but I've already taken care of it.
} answered 19 Jan '15, 17:26

WA in which case ? have been trying since past so many days. help me out ! answered 27 Jan '15, 15:35

Please tell me why am i getting wrong answer for this code. include<stdio.h>int compare(void i1,void i2) { int a=(int )i1; int b=(int )i2; return ba; } int main() { int t,n; int cost[1000]; scanf("%d",&t); while(t) { scanf("%d",&n); int i,totalcost=0; for(i=0;i<n;i++) scanf("%d",&cost[i]); if(n<=2) { for(i=0;i<n;i++) totalcost+=cost[i]; } else { qsort(cost,n,sizeof(int),compare); i=0; while(i<n) { totalcost+=cost[i]+cost[i+1]; i+=4; } } printf("%d\n",totalcost); } return 0; } answered 22 Oct '15, 17:39

https://www.codechef.com/viewsolution/9697384 whats wrong with this solution all the test cases are working correctly ! answered 14 Apr '16, 22:48
