You are not logged in. Please login at www.codechef.com to post your questions!

×

ANUBTG - Editorial

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Minako Kojima
Editorialist: Lalit Kundu

DIFFICULTY:

EASY

PRE-REQUISITES:

Sorting, Greedy

PROBLEM:

You have to buy N items of cost A1, A2 ... AN. 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.
Find minimum price in which you can buy all 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.
- The bag containing x, has only one element.
We can add y in the same bill too because we are anyway paying for both, so why two separated bills instead of one.
- The bag containing x, has more than element. Assume z be the second most costliest item in bag containing x.
Now we can simply swap y and z. So we will end up x and y being in same bag. Also due to this swapping, there is no change in cost because we were anyway paying for both x and y before.

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.
We can even formally prove this part similar to swapping item used in previous claim.

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:

A = input
sort(A)
reverse(A)
ans = 0

for i=0 to N-1:
    //count in answer the index 0,1,4,5,8,9...
    if i%4 < 2:
        ans += A[i]

print ans

Complexity: O(N log N) due to sorting.

SOLUTIONS:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 19 Jan '15, 01:10

darkshadows's gravatar image

5★darkshadows ♦♦
3.0k88158185
accept rate: 12%

edited 19 Jan '15, 01:29

kunal361's gravatar image

4★kunal361
6.0k133272


12next »

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

        sum+=a[i]+a[i+1];


    }
    printf("%d\n",sum);

}
return 0;

}

link

answered 19 Jan '15, 01:31

ankit_vijay's gravatar image

3★ankit_vijay
1
accept rate: 0%

reverted 19 Jan '15, 01:32

try this case:

1

1

1

(19 Jan '15, 01:34) kunal3614★

please give me a test case where my program is getting wrong answer:

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<long long int> inp(10001);
    int t;
scanf("%d",&t);
while(t--){
        int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lld",&inp[i]);
    }
    sort(inp.rbegin(),inp.rend());
    long long int sum=0;
    int con=0;
    for(i=0;i<n;i++){
        if(con<2){
            sum=sum+inp[i];
            con++;
        }
        else{
            i++;
            con=0;
        }

    }
    printf("%lld\n",sum);
}
return 0;
}
link

answered 19 Jan '15, 01:40

deysaikat95's gravatar image

3★deysaikat95
16
accept rate: 50%

edited 19 Jan '15, 01:40

kunal361's gravatar image

4★kunal361
6.0k133272

try this case...

2

2

2 2

1

1

the problem is that u are not clearing your vector for a new test case!!!

(19 Jan '15, 01:47) kunal3614★
1

Thanks! :)

(19 Jan '15, 01:49) deysaikat953★

Such a dumb mistake :(

(19 Jan '15, 01:50) deysaikat953★

my solution is giving wrong answer. please tell me what are mistake in this code??

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
bool str(ll i,ll j)
{
    return i>j;
}
int main()
{
    ll t,n;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        ll u,x,i,a[n+1],sum=0;
        for(i=0;i<n;i++)scanf("%lld",&a[i]);
        sort(a,a+n,str);
        u=n/4;
        x=n%4;
        for(i=0;i<u;i++){
            sum=sum+a[i*4]+a[i*4+1];
        }
        if(x==1) sum=sum+a[u*4];
        if(x==2) sum=sum+a[u*4]+a[u*4+1];
        if(x==3) sum=sum+a[u*4+1]+a[u*4+2];
        printf("%lld\n",sum);
    }
    return 0;
}
link

answered 19 Jan '15, 01:55

ashish_gupta's gravatar image

4★ashish_gupta
1
accept rate: 0%

edited 19 Jan '15, 01:56

kunal361's gravatar image

4★kunal361
6.0k133272

my solution is giving wrong answer. please tell me what is mistake in this code??

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
long int t,n,a[1009],i;
scanf("%ld",&t);
while(t--){
scanf("%ld",&n);
a[1009]={0};
for(i = 0; i < n;i++){
scanf("%ld",&a[i]);
}
long long int sum = 0;
sort(a,a+n,greater<int>());
i = 0;
while(i < n){
sum = sum + a[i]+a[i+1];
i = i+4;
}
printf("%lld\n",sum);
}
return 0;
}
link

answered 19 Jan '15, 03:27

john_123's gravatar image

4★john_123
1
accept rate: 0%

edited 19 Jan '15, 03:29

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[n-1]+cost[n-2];}" else{="" qsort(cost,n,sizeof(int),cmp);="" *for(i="0;i&lt;n;i++)" printf("%d="" ",cost[i]);*="" for(i="n-1;i">=0;i=i-4){ sum=sum + cost[i]+cost[i-1]; } } printf("%ld\n",sum); } return 0; }

link

answered 19 Jan '15, 10:19

nitya's gravatar image

2★nitya
1014924
accept rate: 0%

Please tell why codechef is telling "wrong answer" to this solution. Answers to the given test cases are coming out right.

https://ideone.com/7dZv5U

ps:i used bubble sort. ill use merge later on.

link

answered 19 Jan '15, 13:41

surbhijain93's gravatar image

1★surbhijain93
1
accept rate: 0%

edited 19 Jan '15, 13:41

I had forgotten single input. Sorry, my bad. My doubt is clear

(19 Jan '15, 13:49) surbhijain931★

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.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, const char * argv[]) {

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t,n,s,i;

cin>>t;

while(t--)
{
    cin>>n;

    int A[n+1];

    for(i=0;i<n;i++)
        cin>>A[i];

    s = 0;

    sort(A,A+n,greater<int>());

    for(i=0;i<=n-2;)
    {
        s += A[i];
        s += A[i+1];

        i = i+4;
    }

    if(i==n-1)
        s += A[i];

    cout<<s<<"\n";
}

return 0;

}

link

answered 19 Jan '15, 17:26

anon_user's gravatar image

2★anon_user
132
accept rate: 0%

http://ideone.com/UaAFCt

WA in which case ? have been trying since past so many days. help me out !

link

answered 27 Jan '15, 15:35

raman6194v's gravatar image

3★raman6194v
1
accept rate: 0%

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

link

answered 22 Oct '15, 17:39

shradha_15's gravatar image

1★shradha_15
1
accept rate: 0%

https://www.codechef.com/viewsolution/9697384 whats wrong with this solution all the test cases are working correctly !

link

answered 14 Apr '16, 22:48

paavini's gravatar image

4★paavini
1
accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×9,473
×2,119
×556
×40
×2

Asked: 19 Jan '15, 01:10

Seen: 4,825 times

Last updated: 22 Mar, 11:53