Кажется, все, кому актуально, и так должны знать, но всё же напомню.
Сегодня в час ночи по Москве состоится третий раунд Facebook Hacker Cup. Топ-25 кулхацкеров выходят в финал.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.11.2024 07:58:58 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Ну вообще ад :) Как что решалось?)
Ну в первой у меня формула включения-исключения
Типа как для подсчета беспорядков?
Ога
И как она помогает?
Ну типа f(i) — количество способов подарить подарки так, чтобы не менее i получили подарки из своей же семьи. Считается f(i) так: динамика DP(семья, позиция текущего чувака в семье, сколько подарков в семье мы распределили уже, сколько из i осталось распределить). Так f(i) = DP(0, 0, n[0], i)·(N - i)!, где N — сколько всего чуваков.
По этому штуке запускаем формулу включения-исключения и voilà!
Кстати, решение за O(N2·max(ni)), то есть в данном случае за квадрат, без ограничений на ni — за куб.
20 — будем строить какой-то цикл, начиная из произвольной группы. Это делается динамикой по количеству оставшихся групп каждого размера, а также размерам групп, которые содержат начало и текущий конец цепочки. Аккуратно считаем, не проводя ребер из группы в себя же.
У меня пятимерная динамика. Добавляем чуваков по одному. Добавили уже i чуваков. Пусть D[i][k][a][b][c] — количество способов дойти до состояния, когда у нас:
А дальше смотрим, куда мы можем подцепить очередного и пишем десять, блин, переходов. Я час не мог поверить, что все писали это за десять минут =(
Я уже писал почти абсолютно такую же задачу на TCO-2012
http://community.topcoder.com/stat?c=problem_statement&pm=12183
Ну просто пять баллов =(
Интересно, сколько людей воспользовалось своим кодом =(
Я не воспользовался своим кодом, написал заново. Там было почти (но не совсем) то же самое. Но идея основная такая же, что позволяет написать, практически не думая.
К тому же, чтобы воспользоваться своим кодом, надо быть полуфиналистом TCO-2012
Ну значит так тому и быть. Удачи на финале!
Спасибо
Ну если писать динамику, как выше у Endagorion, то получается вроде меньше. У меня вышло два перехода с похожей динамикой — один в группу какого-то размера (это можно делать в цикле по размерам), другой — в группу, с которой начали. Ну я правда и не дописал все равно :)
Задача же C гуглится по словам "recognizing hamming graphs", но я слишком поздно этим занялся и не осилил написать. Код Макото выглядит в точности как код из статьи.
А это реально придумать, если не знать, что такое граф Хэмминга?
Не знаю. Я не знал, что это так называется, начал свои поиски, когда отчаялся сам придумать, со всяких "rainbow shortest paths". Не помогло. Подумал еще, заметил, что нам надо вписать граф в гиперкуб. "embedding to hypercubes" и "hypercube subgraphs" наконец вывело меня на "hamming graphs" за 40 минут до конца. Даже написал что-то, но не заработало.
Я сам придумал почти то же самое, что у Макото (тоже за O(VE)), но оно не уложилось в 6 минут — неасимптотически медленно написал :(
Круто.
То есть, жаль, что не прошло, но круто, что придумал.
My solution was actually O(E^2) (I used the fact that edge i and edge j should be colored with the same color iff dist[a[i]][a[j]] = dist[b[i]][b[j]] and dist[a[i]][b[j]] = dist[b[i]][a[j]]), but it worked under 15s. It's a pity that your solution timed out.
Интересно видеть такой вопрос от человека, который послал все задачи...
С кодом "Today I was too stupid to solve this problems. So lets have some fun at least for few minutes :)".
У меня на 20 ДП, a[i][j][k] — кол-во способов обработать i семей, при этом j людей из первых i семей ещё не дарили подарка и k людей из первых i семей ещё не получали подарки. Переход вполне простой, и думаю что это можно написать быстро, если не тупить как я. :D
Вообще простое решение :(
j = k
Согласен, спасибо.
Man, that was... definitely harder problems than last year. No AC on the 2nd problem...
I solved the 1st problem with O(K2C) 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 K3, 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...
How have you proven that graph must be planar?
I proved that satisfying the main condition for K3, 3 (as a subgraph) leads to a contradiction.
I'll assume you know the trivial rules for vertices at distance 1.
Firstly, a lemma about K2, 2: let's say that one partition of a subgraph K2, 2 contains vertices (1,2) and the other (3,4); w.l.o.g., associate vertex 1 with a subset S1 of chains, such that no other vertex is associated with a smaller set. Then, for vertices 3 and 4, we have S3 = S1 + a and S4 = S1 + b (a, b are also chains, and a ≠ b), and then S2 = S1 + a + b, because if S2 didn't contain (w.l.o.g.) a, then S2 = S1, which is impossible.
I just realized there's a stroger version, working on any subgraph K2, 3. Let's use the same notation as above (partitions (1,2) and (3,4,5)); S3 = S1 + a, S4 = S1 + b, S5 = S1 + c. There are 2 possible cases: |S1| is the smallest or |S3| is the smallest (w.l.o.g.). If it's S1, then by the lemma on K2, 2 (1,2,3,4) and (1,2,3,5), we have S2 = S1 + a + b = S1 + a + c; otherwise, by the lemma on (1,2,3,4) and (1,2,3,5), we have S4 = S3 + a + b = S5; both are contradictions. QED.
My mistake, it doesn't imply planarity. K3, 3 can be a subgraph of a minor, it just can't be a direct subgraph.
Edge contraction affects the solution, so its off-topic.
It's not edge contraction, though. It's edge deletion. I don't merge the endpoints of an edge, I delete them both.
And just to make this clear: leaves are trivial, so I only consider graphs without leaves.
The fact the graph should be planar isn't true. 5-dimensional binary cube (vertices are numbers from 0 to 31, edges between pair of integers if they differ in exactly one bit) isn't planar, but is easily colorable.
Yeah, my mistake. I just confused the rules of planarity a bit. Still, the planarity was just a peculiar note, not anything important :D, what I was proving back then was non-existence of K3, 3.
Could you elaborate on the first problem. I don't see how your state in dynamic programming is sufficient. My understanding is that it's also important how the other gifts (those that were not added between the processed families) are distributed.
Yes, it is important. It's all hidden in the large constant.
Let's say that we're processing family i, and there are j people so far that haven't given/received (those 2 numbers are equal) any gifts. Out of ni people of this family, x can give gifts to processed people, and y can get gifts from the processed people, moving to a state (i, j + ni - x - y).
Now, combinatorics ensues. Let's assume that the conditions of at least 1 way existing (x, y ≤ j, ni etc.) are satisfied. There are
ways to choose the x people, 
ways to choose y and those 2 groups are independent. There are j(j - 1)..(j - x + 1) ways to choose which people of the j will get gifts from our x, and j(j - 1)..(j - y + 1) ways to choose the same for those giving gifts to the y. Those are just small products and can be enumerated with modular arithmetic in O(ni) = O(1) time.
So even if there are many ways, those are compressed to the combination-variation product; in the dp state, they're viewed as equivalent and they're differentiated only when picking some few of them.
Расскажу, как я решал третью задачу.
Будем сопоставлять не ресторанам множества городов, а городам множества ресторанов. Тогда условие задачи заключается в том, чтобы выбрать множества так, что для каждой пары городов расстояние между ними было равно размеру xor их множеств. В частности, множества соседних городов различаются в одном элементе, а весь граф должен быть двудольным.
Сопоставим каждому ребру номер ресторана, в котором отличаются соединённые им города (будем называть это цветом ребра). Заметим, что цвета рёбер — это всё, что нам нужно: если инвертировать наличие ресторана для всех городов, ничего не изменится. Оказывается, раскрасить рёбра, соблюдая условия задачи, можно не более чем одним способом (с точностью до перестановки цветов). Ответ — число различных цветов.
Пусть мы выбрали ребро AB и хотим найти все рёбра такого же цвета. Будем считать, что в A соответствующего ресторана нет, а в B есть. Рассмотрим на некоторую вершину C. Расстояние от C до A и B будет отличаться на 1 (иначе граф не двудольный). Утверждается, что если C ближе к A, то там этого ресторана нет, а если к B, то есть. Соответственно, если ребро соединяет вершину, которая ближе к A, и вершину, которая ближе к B, то оно того же цвета, иначе нет. Это определяется с помощью BFS из двух вершин.
Так раскрашиваются все рёбра. Если уже проверено, что граф двудольный, и при раскраске ни разу не приходилось красить одно и то же ребро два раза, то можно доказать, что на каждом цикле каждый цвет будет встречаться чётное число раз. Значит, множество цветов, встречающихся на пути из одной вершины в другую нечётное число раз, не зависит от пути. Осталось проверить, что для каждой пары вершин размер этого множества совпадает с расстоянием между ними. Для этого из каждой вершины с помощью BFS считается расстояние, затем DFS с отслеживанием множества (и его размера) всё проверяет.
Итоговая сложность O(nm), у меня работало 50 секунд.
Да, у меня ровно то же самое, но написал плохо, не уложилось в 6 минут. Слишком много объектов. Обидно :(
Всё, перестаю жаловаться. Удачи на финале!
(удалил повторный комментарий)
А я вот не проверил после покраски, и на 1 из 20 тестов она выдала не -1 а кое-что другое. Блин. :)
.
У кого есть аватарка — смотрим url, например https://fbcdn-profile-a.akamaihd.net/hprofile-ak-prn2/275990_100001480955629_978807598_q.jpg
Значит его страница в лицекниге: https://www.facebook.com/100001480955629
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.
Also, Wikipedia had the answer to the problem.
http://en.wikipedia.org/wiki/Partial_cube
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
It was pointed out to me that the max flow construction itself is a proof. We can always saturate the network with fractional flows because S_i is a multiple of C_i and therefore there is an integer solution as well.
Is there any link to the problems too?
T-Shirts are coming! Got mine today.
Anybody knows, it is OK that i have not received my t-shirt yet?
Yeah, sending t-shirts always takes a lot of time for some reason.