VK cup eliminations — Levels and Regions — higher limits

Revision en2, by Radewoosh, 2016-08-21 19:41:55

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

I'm posting solution below this text, if you want to read it just scroll down.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

SOLUTION ALERT

There are two key observations.

  1. Obviously, higher k means smaller result.
  2. For every i (1 < i < n) there is res(i + 1) - res(i) ≤ res(i) - res(r - 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.

SOLUTION ALERT

Tags after ioi, challenge, dp, convex hull optimization, complexity optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Radewoosh 2016-08-22 01:12:03 2 Tiny change: 'es(i)-res(r-1)$.\n\nT' -
en4 English Radewoosh 2016-08-21 19:51:28 7 Tiny change: 'n? :D\n\n\n\n\n 'n? :D\n\n\\\n\n\n
en3 English Radewoosh 2016-08-21 19:48:43 305 Tiny change: ' n? :D\n\nI'm posting solution below.\n\n\n ' n? :D\n\n\n\n\n
en2 English Radewoosh 2016-08-21 19:41:55 1505 Tiny change: 'n below that text, if ' -
en1 English Radewoosh 2016-08-21 18:21:50 393 Initial revision (published)