There are two key observations.
- Obviously, higher k means smaller result.
- For every i (1 < i < n) there is res(i + 1) - res(i) ≤ res(i) - res(i - 1).
The above implies that for every i (that 1 ≤ i ≤ n) there exists such real value X that res(i) + i·X ≤ res(j) + j·X for every . Also, for fixed i good X's are between res(i + 1) - res(i) and res(i) - res(i - 1), inclusive (except for trivial cases k = 1 and k = n).
So, when we have fixed X, we can calculate the minimum value of dividing sequence into intervals (we can use any number of them), where cost for an interval is the same as in the basic version of task plus X. Using the convex hull trick, we can do it in O(n). Then we check how many intervals we've used to do it. If we've used too many, we know that X should be greater (to force the algorithm to use smaller number of intervals). If we've used at most k intervals, we should make X lower. So now we see that we should use binary search to find good X!
After finding good X, we just calculate the optimum value for full sequence and subtract k·X. This gives us O(n·log) solution.
I'm really interested if it's the first appearance of this nice idea on IOI?
You mean full solution of P6? Could you explain its solution. Couldn't understand Swistak's comment.
Well, I think it's not good idea to write it here. I can send it to you in PM.
I'll post solution in few minutes. :)
Trick to get from O(n*k) to O(n*log) is same in both tasks, so you can try to understand this one.
How to construct the answer in general case?
It was possible to use this technique in the problem 739E - Гоша выходит на охоту. In this problem there could be a case where res(k + 1) - res(k) = res(k) - res(k - 1) where k is the value that we are looking for. This implies that there is no real value X which selects exactly k things. It is still quite easy to find the value of the answer by using this technique. However constructing the configuration that gives the answer seems to be really hard and I can't figure out how to do it. Does anyone know a general way to construct the answer when using this technique and the function is not strictly convex?
Hello,
Can anyone explain this method in other words, I can't fully get the idea. in particular, what is res(i)? is it optimal solution when K=i ? if yes then res(i + 1) - res(i) should be negative because of observation 1. also how could those observations imply " res(i) + i·X ≤ res(j) + j·X " ?
How did you prove res(i + 1) - res(i) ≤ res(i) - res(i - 1)? Radewoosh
Consider some partition of [1, n] into M disjoint intervals , and define . Let P * M be a partition that minimizes over partitions with M elements. Then we define
(and for partitions that aren't optimal over their number of elements, we set to 0 everywhere).
Then each is convex, and is also convex.
EDIT: Wow, this is completely wrong -- I have magically managed to show that is convex, but it was supposed to be concave!! It isn't hard to fix; if you switch to a more natural definition of (for a partition into M parts -- optimal or otherwise):
then is concave (and not convex like I said earlier -- oof), and is the min over all .