By Radewoosh, history, 4 years ago, Hi guys!

On IOI I've learned many new things, so now I want to give you a challenge. You probably remember my and Errichto's eliminations to VK Cup 2016. Let's focus on this problem: 674C - Levels and Regions

Main solution was solving it in O(n*k), because k wasn't greater than 50. What if k is just lower or equal to n? :D

solution dp, Comments (10)
 » 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 - Gosha is hunting. 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 " ?
 »
 » 4 years ago, # | ← Rev. 2 →   How did you prove res(i + 1) - res(i) ≤ res(i) - res(i - 1)? Radewoosh
•  » » 20 months ago, # ^ | ← Rev. 2 →   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 .