I think that the solution of editorial for the mentioned problem is incorrect.
Link for official editorial solution:(https://discuss.codechef.com/questions/77148/amr15d-editorial/“title”
It says to sort the input array and pick up the Smallest ⌈N/(K+1)⌉ coins.
However lets say we give an already sorted input 1 2 3 95 96 97 and k=2
the editorial solution prints 6
However the answer as per my understanding of the question should be (1+95)=96
please someone clarify this doubt.
No, the editorial solution is right but it will print 3(not 6) for your case as (N/k+1)=6/3=2; sum of value of he will pay at both the houses is 1+2=3 .
First he will buy 1 gold plate from house number 1 and loot the houses containing 95 and 96 gold plates (house 4 and 5) and acquire them for free then he will buy 2 gold plates from house number 2 and loot the houses containing value 97 and 3 gold plates(houses 3 and 6) and acquire them for free. So, total amount = 1+2=3
Got it… i was presuming that he picks up k adjacent houses … .my bad
Thanks again
No problem!