SEERC 2010 - Codeforces

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

SEERC 2010

Автор Aziza, 13 лет назад, По-русски

Подскажите как решить задачу D или G?

http://acm.ro/2010/index.html

http://www.e-olimp.com/en/competitions/499 суда можно сдать

#seerc, strings, zalgorithm

Aziza
13 лет назад
18

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

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

mexmans

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

Не уверен, но может быть в D: перебираем маску контестов, которые будем проводить, для каждой такой маски пустим поток (используем только те контесты из маски), и проверим насытили ли мы все контесты. А где можно сдать эти задачи?

→ Ответить

JKeeJ1e30

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

Эта задача так решается, но лучше ее сдавать следующим образом: каждый контест размножим на количество задач и найдем полный парсоч. В таком виде получаем такую же ассимптотику, но с меньшей константой.

→ Ответить

Aziza

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

я так написала, тайм лимит :((

→ Ответить

JKeeJ1e30

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

хммм... Интересно. А если перебирать маски кодами Грея? В этом случае мы можем использовать уже построенный на предыдущем ходу парсоч - если +1 бит, то мы ищем увеличивающие цепи, если -1 бит - то убираем ребра, ведущие в этот бит, и ищем увеличивающую цепь.

→ Ответить

JKeeJ1e30

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

← Rev. 3 →

хммм. Можно даже так. Будем идти обходом в ширину по маскам, где ребро - это прибавление одного бита, запускаемся от нулевой маски. Очевидно, что если парсоч для данной маски уже не полный - значит, если мы будем добавлять биты, мы полный парсоч не получим. То есть, запускаемся только от тех масок, где получен уже полный парсоч, и в них ищем увеличивающую цепь. Асимптотику как посчитать в таком варианте решения я не знаю, но это в разы быстрее чем для каждой маски строить парсоч - во-первых, мы отсекаем явно невалидные маски, во-вторых, мы ответ достраиваем, а не строим с самого начала.

→ Ответить

Aziza

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

← Rev. 3 →

post0

→ Ответить

Aziza

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

→ Ответить

Aziza

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

piwu piwu pustoe soobwenie polu4aetsya ?! potom tam je ocenka O(2^15 * n^2 * m^2 * 7), nu esli potok s maswtabirovaniem pisat ))

→ Ответить

maksay

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

Насколько я помню, в основном народ сдавал или перебор подмасок в порядке кода Грея (тогда не надо было пересчитывать весь поток, а только идущий через определенную вершину) или просто накодил быстрый поток (у нас Диниц зашел без проблем).

→ Ответить

I_love_Tanya_Romanova

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

Я D решат через теорему Холла. Т.е. для каждой маски проверял, удовлетворяет ли она условия т. Холла. Для подмасок можно считать только 1 раз - получаем динамику, перебор подмасок от меньшего числа единиц к большему.

→ Ответить

olpetOdessaONU

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

С теоремой Холла очень красивое решение.

→ Ответить

olpetOdessaONU

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

Все ответы пока что были про D, которая выглядит более простой. Куда интереснее услышать решение задачи G. Помню, что довольно долго думал над ней и в итоге придумал такое ужасное решение, которое не было никакого желания кодить.

→ Ответить

AWPRIS

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

← Rev. 2 →

Если G - это "Выбор фотоаппарата", то по ней есть авторский разбор решения И.Н.Порублёва - если очень интересует, могу выложить, думаю Илья Николаевич возражать не будет. :)

UPD(на реплику ниже): понял, не туда. Где-то я видел её разбор, но на английском. Как попадется под руки, то коль уже здесь не в тему отписался, то обязательно выложу разбор по теме. :)

→ Ответить

olpetOdessaONU

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

Анатолий Васильевич, мы обсуждаем SEERC-2010, тут G - это Cosmic Station или как-то так.

С задачей этого года мы уже разобрались и сдали её на зеркале Второй Лиги.

→ Ответить

goo.gl_SsAhv

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

ну задача G довольно просто решается. будем строить дерево.

найдем две самых удаленных вершины, и между ними построим кишку с нужным числом вершин (по величине этого макс расстояния). теперь давай рассмотрим некоторый рекурсивный процесс на входе у нас есть две вершины(станции) - края кишки, сама кишка в некотором векторе, а также список станций которые как-то должны ответвляться от этой кишки. изначально это кишка что мы построили по макс расстоянию, а в списке вершин все остальные вершины кроме краёв кишки. A и B - края, С-некоторая другая вершина тогда x=(d[a][c] + d[b][c] - d[a][b]) / 2 - расстояние от кишки, до вершины C, расстояние от A до того места на кишке, где будет ответвляться поддерево с вершиной C это d[a][c] - x. просмотрим весь список вершин и для каждой определим место ответвления, теперь сгруппируем вершины по этому месту и определим новые списки. из каждого списка нужно взять самую дальнюю вершину C (от A например) и построить цепь от места ответвления до С. запускаем рекурсивно ту же процедуру но с параметрами A' = A, B' = C, кишку заменяем на часть кишки от A до места ветвления, плюс (конкатенация) цепь от места ветвления до C, список вершин это тот список в котором была вершина C за минусом её самой. ну и т.д. рекурсивно.

→ Ответить

olpetOdessaONU

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

Спасибо. Идея была схожая, но без рекурсивного перехода. Поэтому реализация предполагалась страшная.

→ Ответить

vitar

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

← Rev. 2 →

По скольку нам надо вывести не само дерево, а только число вершин в нём, то можно всё сделать попроще.

Рассмотрим некоторый лист нашего дерева. К этому листу от ближайшей к нему развилки (развилка это вершина степени >= 3) ведёт цепочка. Найдём длинну этой цепочки. Alias уже почти написал как. Зафиксируем произвольно начало его кишки, переберём все остальные вершины в качестве конца. И из всех 'x' - расстояний до кишки выберем минимальное. Это и будет расстояние до ближайшей развилки. Добавим его к ответу. После чего нашу вершину, вместе с цепочкой ведущей к ней, удалим из дерева. Тоесть просто больше никогда не будем её рассматривать в качестве конца кишки. И так сделаем для каждой вершины.

Получаем 2 вложенных фора (перебираем вершину и для каждой вершины перебираем конец кишки) и одна формула рассчёта расстояния до кишки внутри. Пишется 5 минут.

→ Ответить