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

ICPC subregional Saint Petersburg 4 November (?: F, G, H)

Автор Mano, история, 7 лет назад, По-английски

Всем привет!) Расскажите пожалуйста как решались задачи с минувшего четвертьфинала в Санкт-Петербурге (4 ноября). Интересуют F, G, H.

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Which division you are considering?

Div1 problems: https://neerc.ifmo.ru/archive/2017/northern/north-2017-statement.pdf

Div2 problems: https://neerc.ifmo.ru/archive/2017/kazakhstan/northern-lite-2017-statement.pdf

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Div1

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I also want to know their solutions, also problem D. (thought D of div2 was pretty easy, but seems there are very few teams who solved D in div1)

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I did not read this problem) We will wait for tutorial together)

        → Ответить
»
7 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Помогите пожалуйтса с задачей L. Какие могут быть частные случаи. Получаю WA на 19-ом тесте

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://neerc.ifmo.ru/archive/2017/northern/north-2017-analysis.pdf

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А был где-нибудь видео-разбор? Из презентации мало что понятно.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я тоже хотел бы найти полный текстовый/видео разбор. Но пока нашлась только эта презентация.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Есть надежда что кто-нибудь сюда заглянет своим решением поделится)

        → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Разбор должен был быть, но из-за задержки соревнования решили сразу преступить к разморозке/награждению.
      Там ещё есть архив с решениями от жюри, может он поможет.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
G
H
→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

F.

Нам гарантировалось, что все циклы строго вложены и есть ровно один lag.

Каждый цикл имеет форму

for i in range(j, k)

Из этого следует, что j ≤ i, i ≤ k. Построим из переменных в циклах граф, каждое ребро в таком графе соответствует отношению  ≤  (если i = 1 или k = n, то соответствующее ребро опускается), нужно посчитать число способов выбрать каждую переменную от 1 до n, чтобы граф отношений был корректен.

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

Особый случай если в графе есть цикл. Тогда все эти переменные равны друг другу, можно этот цикл сжать и запустить решение от меньшего графа.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

G.

Рассмотрим остов DFS. Каждое ребро вне этого остова порождает некоторый простой цикл в исходном графе, причём каждому такому циклу соответствует какой-то вертикальный путь в дереве.

Если существует два таких dfs-цикла, пути которых пересекаются по хотя бы одному ребру, то они образует ответ (общая часть является одним из путей, две другие берутся из циклов), если таких нет, то наш граф является кактусом, в нём ответа нет.

Как проверить и найти пересекающиеся пути? На самом деле достаточно просто. Для кажого ребра остовного дерева будем сохранять допрёбра, проходящие через него. Когда мы в dfs-е обнаруживаем допребро (и ему соответствующий цикл), то явно проходим по каждому ребру в пути соответствующему этому циклу и добавляем дополнительное ребро в соответствующий список.

Если после добавления в списке окажется 2 дополнительных ребра, то вот оно пересечение.

Время работы линейное, так как в каждый список добавим  ≤ 1 элемента.

→ Ответить