Editorial for COCI '22 Contest 1 #2 Čokolade


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First, let us observe that the order of chocolates, does not matter, so we can sort them. Equivalent to the value l-f is to sum the value l-f of every chocolate separately. If we need one chocolate, it would be optimal to take the most expensive or the cheapest chocolate. The reason why that is the case is described in the condition of the task:

  • If the chocolate is cheaper than k kunas, Lana will pay full price and therefore she would like to take the chocolate with the smallest price possible.
  • If the chocolate is more expensive than k kunas, the value l-f for that chocolate will be equal to k-(c-k) = 2k-c. So, the more expensive chocolate is, the better.

With this, we can solve the first partial. If we split the chocolates into two categories (c \le k and c > k), we can iterate over the number of cheaper chocolates. If Lana takes x chocolates cheaper than k (first x chocolates in the sorted sequence), she will take m-x expensive (last m-x chocolates). Time complexity is \mathcal O(nq).

Let us look at this example: Consider a query with k = 7 and m = 4.

Four numbers are larger than 7, and four are smaller. Let us assume that we want to take all four chocolates smaller than k. Can we make the required value smaller? The answer is yes. If we would instead of the chocolate that costs 6 kunas (value 6) take the chocolate that costs 20 kunas (value -6), the total value would be smaller. If we compare the next two possible chocolates from the ends (5 and 15), we can see that 5 has a value of 5, and 15 has a value of -1, so it is even better to take two of the chocolates from the right end! With that step, we have reached the best solution (1, 2, 15, 20) (because the values of the next two chocolates are 2 and 4, so the chocolate with the price 2 has a smaller value than the chocolate with the price 11). It is enough to binary search the number of chocolates we are taking with the smaller than k for each query with the same check we were making in the paragraph above. For every query that will be \log operations. Total time complexity is \mathcal O(q \log n).


Comments

There are no comments at the moment.