Radewoosh's blog

VK cup eliminations — Levels and Regions — higher limits
By Radewoosh, history, 8 years ago, In English

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

Unable to parse markup [type=CF_TEX]

solution
  • Vote: I like it
  • +98
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I'm really interested if it's the first appearance of this nice idea on IOI?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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 " ?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

How did you prove res(i + 1) - res(i) ≤ res(i) - res(i - 1)? Radewoosh

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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 .

    → Reply