PROBLEM LINK
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)