PROBLEM LINKPanel MembersProblem Setter: Suhash 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. EXPLANATIONIt 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<=n1; 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_needed1; 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<=n1; i++) { cin >> arr[i]; } sort(arr, arr+n); for(int i=1; i<=n1; i++) { arr[i] += arr[i1]; } while( q ) { cin >> k; int coins_needed = ceil(1.0*n/(k+1)); int ans = arr[coins_needed1]; cout << ans << "\n"; } return 0; } COMPLEXITY$O(Nlog(N) + Q)$ SIMILIAR PROBLEMS
This question is marked "community wiki".
asked 17 Nov '15, 03:14

Can someone explain , why are we choosing (N / (k+1) ) coins answered 24 Jan '16, 20:22

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)
N * x/(K + x) answered 26 Sep '16, 02:29

There is a problem with the editorial code
q is at the end of the arr input answered 15 Oct '16, 17:53

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[nk1]<<endl; to ul c_n = ceil(1.0*n/(k+1)); cout<<res[c_n1]<<endl; answered 21 Oct '16, 21:07

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 answered 21 Apr '17, 11:30

in the given question it is given that it can loot at most k houses. so how can we claim thatIt 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 answered 10 Oct '17, 21:06
