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

×

AMR15D - Editorial

PROBLEM LINK

Practice
Contest

Panel Members

Problem Setter: Suhash
Problem Tester:
Editorialist: Sunny Aggarwal
Contest Admin:
Russian Translator:
Mandarin Translator:
Vietnamese Translator:
Language Verifier:

DIFFICULTY:

Easy

PREREQUISITES:

Basic Mathematics, Prefix Sum, Sorting, Dynamic Programming.

PROBLEM:

Given a list of $N$ coins of possibly different denominations. We can pay amount equivalent to any $1$ coin and can acquire that coin. In addition once we have paid for a coin, we can choose atmost $K$ more coins and can acquire those for free. What is the minimum amount required to acquire all the $N$ coins for a given $K$ ?

Note that a coin can be acquired only once.

EXPLANATION

It is easy to notice that at a cost of $1$ coin, we can acquire at most $K+1$ coins. Therefore, in order to acquire all the $N$ coins we will be choosing $\lceil N/(K+1)\rceil$ coins and the cost of choosing coins will be minimum if we choose smallest $\lceil N/(K+1)\rceil$ coins. Smallest $\lceil N/(K+1)\rceil$ coins can be found by simply sorting all the $N$ values in increasing order.

C++ code:

int main() {
    int n, k;
    cin >> n >> k;
    int arr[n];
    for(int i=0; i<=n-1; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+n);
    int coins_needed = ceil(1.0*n/(k+1));
    int ans = 0;
    for(int i=0; i<=coins_needed-1; i++) {
        ans += arr[i];
    }
    cout << ans << "\n";
    return 0;
}

As we are asked to find the above answer for many different values of $K$, we have to compute it fast. For the purpose to serve, we can maintain a prefix sum array after sorting all the $N$ values and can answer queries easily.

C++ code:

int main() {
    int n, q, k;
    cin >> n >> q;
    int arr[n];
    for(int i=0; i<=n-1; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+n);
        for(int i=1; i<=n-1; i++) {
        arr[i] += arr[i-1];
    }
    while( q-- ) {
        cin >> k;
        int coins_needed = ceil(1.0*n/(k+1));
        int ans = arr[coins_needed-1];
        cout << ans << "\n";
    }
    return 0;
}

COMPLEXITY

$O(Nlog(N) + Q)$

SIMILIAR PROBLEMS

Ruspa And Game

Query Over Matrix

Minimum Maximum

This question is marked "community wiki".

asked 17 Nov '15, 03:14

ma5termind's gravatar image

3★ma5termind
1.6k1229
accept rate: 11%

edited 04 Feb '16, 13:27

admin's gravatar image

0★admin ♦♦
14.3k347483501


Can someone explain , why are we choosing (N / (k+1) ) coins

link

answered 24 Jan '16, 20:22

bhishma's gravatar image

4★bhishma
2065
accept rate: 11%

Hello bhishma,

At a cost of 1 coin we can acquire at most K (free coins) + 1 (paid coin). that is


for getting K+ x coins we need to pay x (cost)
so for getting N coins we need to pay


N * x/(K + x)

link

answered 26 Sep '16, 02:29

maheshuligade's gravatar image

2★maheshuligade
1
accept rate: 0%

There is a problem with the editorial code

cin>>n>>q;

q is at the end of the arr input

link

answered 15 Oct '16, 17:53

p1y1_3's gravatar image

2★p1y1_3
1
accept rate: 0%

https://www.codechef.com/viewsolution/11895664 is giving wrong ans and https://www.codechef.com/viewsolution/11895767 is accepted . the only line i changed was from cout<<res[n-k-1]<<endl; to ul c_n = ceil(1.0*n/(k+1)); cout<<res[c_n-1]<<endl;

link

answered 21 Oct '16, 21:07

rishabh1906's gravatar image

3★rishabh1906
1
accept rate: 0%

can't understand the question...what if i give n=16 and values will be 22,21,18,17,15,13,12,11,9,8,7,5,4,3,2,1 and k=22,21,7,6,10,8,2,3,23 ,please expalin for these

link

answered 21 Apr, 11:30

vivek7119's gravatar image

2★vivek7119
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,879
×2,146
×871
×412
×109
×51
×3

Asked: 17 Nov '15, 03:14

Seen: 3,231 times

Last updated: 21 Apr, 11:30