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

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

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


http://www.e-olimp.com/en/competitions/499 суда можно сдать
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Не уверен, но может быть в D: перебираем маску контестов, которые будем проводить, для каждой такой маски пустим поток (используем только те контесты из маски), и проверим насытили ли мы все контесты. А где можно сдать эти задачи?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Эта задача так решается, но лучше ее сдавать следующим образом: каждый контест размножим на количество задач и найдем полный парсоч. В таком виде получаем такую же ассимптотику, но с меньшей константой.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      я так написала, тайм лимит :((
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        хммм... Интересно. А если перебирать маски кодами Грея? В этом случае мы можем использовать уже построенный на предыдущем ходу парсоч - если +1 бит, то мы ищем увеличивающие цепи, если -1 бит - то убираем ребра, ведущие в этот бит, и ищем увеличивающую цепь.
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    post0
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
piwu piwu pustoe soobwenie polu4aetsya ?! potom tam je ocenka O(2^15 * n^2 * m^2 * 7), nu esli potok s maswtabirovaniem pisat ))
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Насколько я помню, в основном народ сдавал или перебор подмасок в порядке кода Грея (тогда не надо было пересчитывать весь поток, а только идущий через определенную вершину) или просто накодил быстрый поток (у нас Диниц зашел без проблем).
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Я D решат через теорему Холла. Т.е. для каждой маски проверял, удовлетворяет ли она условия т. Холла. Для подмасок можно считать только 1 раз - получаем динамику, перебор подмасок от меньшего числа единиц к большему.
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Все ответы пока что были про D, которая выглядит более простой. Куда интереснее услышать решение задачи G. Помню, что довольно долго думал над ней и в итоге придумал такое ужасное решение, которое не было никакого желания кодить.
→ Ответить
  • »
    »
    13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Анатолий Васильевич, мы обсуждаем SEERC-2010, тут G - это Cosmic Station или как-то так.
      С задачей этого года мы уже разобрались и сдали её на зеркале Второй Лиги.
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        ну задача 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 за минусом её самой. ну и т.д. рекурсивно.
        → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Спасибо. Идея была схожая, но без рекурсивного перехода. Поэтому реализация предполагалась страшная.
          → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

           

          → Ответить