VK cup eliminations — Levels and Regions — higher limits

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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

Комментарии (9)

Показать архивные | Написать комментарий?

vintage_Vlad_Makeev

8 лет назад, # |

+13

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

→ Ответить

shym_orange

8 лет назад, # ^ |

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.

Radewoosh

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.

Laakeri

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?

kingofnumbers

+11

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

zscoder

← Rev. 2 →

+15

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

polingy

6 лет назад, # ^ |

Consider some partition of [1, n] into M disjoint intervals $\text{[math]}$ , and define $\text{[math]}$ . Let P^*_M be a partition that minimizes $\text{[math]}$ over partitions with M elements. Then we define

$\text{[math]}$

(and for partitions that aren't optimal over their number of elements, we set $\text{[math]}$ to 0 everywhere).

Then each $\text{[math]}$ is convex, and $\text{[math]}$ is also convex.

EDIT: Wow, this is completely wrong -- I have magically managed to show that $\text{[math]}$ is convex, but it was supposed to be concave!! It isn't hard to fix; if you switch to a more natural definition of $\text{[math]}$ (for a partition into M parts -- optimal or otherwise):

then $\text{[math]}$ is concave (and not convex like I said earlier -- oof), and $\text{[math]}$ is the min over all $\text{[math]}$ .

Блог пользователя Radewoosh