Ну вообще ад :) Как что решалось?)

Man, that was... definitely harder problems than last year. No AC on the 2nd problem...

I solved the 1st problem with O(K²C) dynamic programming, taking (number of processed families, number of gifts added between them) as a state; C is some large constant here, if we consider the size of a family to be constant — and small.

I realize that if the 2nd problem looks really easy, costs that many points, and is in the last round, it will be something really hardcore, so I never even tried to code anything on it :D

I spent most of the time on the 3rd problem, and managed to prove that the graph must be bipartite, planar (there's no solution for K_3, 3) and got to the assumption that is must be reducible to a single edge by the operation "find 2 connected vertices of degree 2 and delete them". Is it good or completely off-topic? :D

Still, top 50 is good enough...

Расскажу, как я решал третью задачу.

Будем сопоставлять не ресторанам множества городов, а городам множества ресторанов. Тогда условие задачи заключается в том, чтобы выбрать множества так, что для каждой пары городов расстояние между ними было равно размеру xor их множеств. В частности, множества соседних городов различаются в одном элементе, а весь граф должен быть двудольным.

Сопоставим каждому ребру номер ресторана, в котором отличаются соединённые им города (будем называть это цветом ребра). Заметим, что цвета рёбер — это всё, что нам нужно: если инвертировать наличие ресторана для всех городов, ничего не изменится. Оказывается, раскрасить рёбра, соблюдая условия задачи, можно не более чем одним способом (с точностью до перестановки цветов). Ответ — число различных цветов.

Пусть мы выбрали ребро AB и хотим найти все рёбра такого же цвета. Будем считать, что в A соответствующего ресторана нет, а в B есть. Рассмотрим на некоторую вершину C. Расстояние от C до A и B будет отличаться на 1 (иначе граф не двудольный). Утверждается, что если C ближе к A, то там этого ресторана нет, а если к B, то есть. Соответственно, если ребро соединяет вершину, которая ближе к A, и вершину, которая ближе к B, то оно того же цвета, иначе нет. Это определяется с помощью BFS из двух вершин.

Так раскрашиваются все рёбра. Если уже проверено, что граф двудольный, и при раскраске ни разу не приходилось красить одно и то же ребро два раза, то можно доказать, что на каждом цикле каждый цвет будет встречаться чётное число раз. Значит, множество цветов, встречающихся на пути из одной вершины в другую нечётное число раз, не зависит от пути. Осталось проверить, что для каждой пары вершин размер этого множества совпадает с расстоянием между ними. Для этого из каждой вершины с помощью BFS считается расстояние, затем DFS с отслеживанием множества (и его размера) всё проверяет.

Итоговая сложность O(nm), у меня работало 50 секунд.

.

Funny that C appeared on team competition in Poland 2 weeks ago :P (problem M here http://www.mwpz.poznan.pl/zadania.php). In slightly different version, but main idea was exactly the same. Nobody solved it during the contest, but few guys successfully googled it :P.

Here's a solution to Pizza Baking (the second problem).

Let S_i be the total number of pizzas that need to be in an oven at time i. Then the key lemma to this problem is that the number of ovens needed to satisfy the requirements is always max(ceil(S_i / C_i)). While it's an obvious lower bound I still don't have a clean proof of its correctness.

Given this lemma, we first calculate the number of required ovens, call it M. Then we'll add a virtual pizza at every time so that S_i = C_i * M at all times. Therefore it will be necessary to fill every oven to maximum capacity at all times.

We can find such an assignment that fills the oven to capacity using max flow. To do so we will have K + 1 nodes for each time. Then for each pizza we'll connect its start time to its end time (where the times are in [s, e) form instead of the [s, e] form given in input). Now imagine that there are capacities from the source to the time nodes and from the time nodes to the sink node. Then we can compute the number of pizzas selected by the flow at time i as sum[j<=i] flow[source][j] — flow[j][sink]! Therefore we just need to setup the capacities from the source and sink nodes to time nodes so that in a maximal flow the oven is at capacity at all times.

Therefore we should set cap[source][i] = max(0, C[i] — C[i — 1]) and cap[i][sink] = max(0, C[i — 1] — C[i]).

Now we use this flow concept and try forcing pizzas to be used and verifying that a feasible solution still exists. If we reuse old flow networks this can lead to a rather efficient solution.

Code: https://gist.github.com/msg555/8078816

T-Shirts are coming! Got mine today.

Anybody knows, it is OK that i have not received my t-shirt yet?