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

2 Likes

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

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)

There is a problem with the editorial code

cin>>n>>q;

q is at the end of the arr input

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;

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

in the given question it is given that it can loot at most k houses.
so how can we claim that–It is easy to notice that at a cost of 1 coin, we can acquire at most K+1 coins.
if k=2 then we can at cost of 1 coin then we should be able to acquire at most K+1=3 coins.
which is contradicting the given example