Блог пользователя ant.ermilov

Автор ant.ermilov, 11 лет назад, По-русски

Кажется, снова никому не пришло письмо.
Так что напомню, что сабж будет сегодня в 20:00 Москвы.

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

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

у кого-нибудь получается приконнектиться к арене?

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

Мне одному показалось, что сегодня задачи были заметно сложнее чем обычно?

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

По поводу 1000. На контесте научился сводить к матожиданию диаметра. Надо как-то научиться его считать или что-то совсем другое?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Да. Фиксируем центр — это либо вершина, либо центр ребра. А дальше расширяемся с этого места в 4/2 стороны. У нас должно быть по вершине на 2х краях — там уже формула включения/исключения

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Что-то я туплю. Почему в тесте №5 выигрывает Боб?

Не правильно распарсил условие

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

    Рассмотрим ходы Алисы. Если она ходит в большой круг, в котором 4 вложенных — Боб оставляет ее с этими кругами и выигрывает. Если она ходит в один из 4-х маленьких — тогда Боб оставит ей еще один круг и выигрывает.Остальные случаи симметричны.

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

Как решать медиум? Я пробовал так — искал вложенности, потом считал функцию Гранди для каждого круга(переход — или ставим точку в большой круг и разбиваем на сумму игр для прямых детей, или ставим точку в одного из детей и разбиваем на сумму игр для остальных). Но такое решение не проходит 1 сеймпл, потому-что там возможен ход в круг, у которого функция Гранди равна нулю. Как с таки бороться?

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

    Переход: точку можно ставить куда угодно, а не только в корень и в его непостредственных детей.

    А вот моя интуиция сегодня тупанула, подсказав мне что функция Шпрага-Гранди от графа — высота дерева, что довольно хорошо выполнялось на маленьких графах...

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

      Да, понял ошибку, спасибо.

      Правда странно, что оно падает на тесте где максимальная глубина вложенности равна 1

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

    Функция Гранди одного круга 1.

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

    Ход = отрезать путь от корня до какой-то вершины. При этом понятно что отпадает. Для каждой вершины посчитали ответ для всего поддерева, потом dfs'ом посчитали ее функцию гранди. Как посчитать что отвалится вроде понятно. Если нет, то проще посмотреть код чем объяснять наверное.

    PS. Ни чем от отличается от того, что у вас, ни в чем у вас проблема я так и не понял.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Так решать нельзя, потому что в этом решении мы форсируем порядок ходов.

    Я решал так. Будем считать функцию Гранди от поддеревьев. Пусть у нас есть дерево с корнем в какой-то вершине V. Тогда пусть S(V) — это множество всех вершин из ее поддерева (включая ее саму). Мы можем походить в любую из вершин множества S(V) — переберем ее (пусть это X). Тогда на какие игры разобьется наша исходная игра? Легко видеть, что это игры для всех компонент связности, которые останутся после удаления пути из X в V. Следовательно, нам надо просто проксорить функции Гранди для соответствующих поддеревьев. Ну а дальше взять mex, чтобы найти функцию Гранди для поддерева с корнем в вершине V.

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

I cant participate because no e-mail notification.