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

Автор tiom4eg, 10 месяцев назад, По-русски

Привет, Codeforces.

Вчера закончился длинный тур Открытой олимпиады этого года, который проходил с 25.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.

А на 100 баллов
B на 91 (100?) баллов
C на 30 баллов
D на 100 баллов
E на 89 (100?) баллов
F на 91 балл
G на 100 баллов
H на 82 (100?) баллов
I на 60 баллов

Спасибо за внимание.

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

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

Для задачи I, aliens trick (вроде его лямбда-оптимизацией кличут) заходит на 100. Пересчет дп аналогичный как в более ранних подзадачах, без учёта лишнего измерения; восстановление ответа чуть сложнее, но возможно благодаря танцам с бубном и шаманским пляскам, выводится с использованием бумаги и ручки довольно быстро, самое сложное — реализовать. Чуть позже прикреплю код если кому интересно)

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

    Написал я этот ваш инопланетянский трюк, не понял правда за что свой сон отдал.

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

    Опишу альтернативный подход, он уже встречался вот тут https://mirror.codeforces.com/gym/102331/problem/J

    Будем решать задачу для всех k, а также держать в голове HLD дерева. Идея состоит в том, что нам нужно знать честные вектора динамики только для самых верхних вершин в тяжёлых путях. То есть алгоритм подсчёта может быть таким: для всех лёгких детей получить правильное значение динамики разделяйкой по их тяжёлому пути; объединить значения лёгких детей (тоже разделяйкой). Итого мы для вершины получим значение динамики без учета тяжёлого сына; как раз это значение и будет использоваться, когда понадобится правильное значение от верхней вершины текущего тяжёлого пути. Та, что по тяжёлому пути, совпадает с решением подзадачи на массиве (ОП рассказал). Та, что по лёгким детям, почти полностью повторяет мерж детей в рюкзаке за квадрат (и тут ОП помог). O(n log^2 n) времени, O(n log n) памяти, значительные константы.

    Восстановление ответа сводится к запоминанию, когда делаем сумму Минковского, из каких индексов аргументов мы пришли. Граф этой штуки примерно такой — вот мы в корне, спустились по разделяйке для его тяжелого пути; там в листьях — корни разделяек по лёгким детям; у них в листьях — корни разделяек по тяжёлым путям и т.д. К сожалению, прямо так в память это не влазит. Запоминать только корни и листья, а промежуточные вершины каждый раз пересчитывать (лишний log в асимптотике) — не влазит по времени. Поэтому нужен trade off, а именно сделаем кеш для бедных — будем запоминать лишь вершины на глубине <= 2 от корня разделяйки; как только понадобилась какая-то более глубокая — пересчитываем (тоже с запоминанием на глубине <= 2). Кажется, формально асимптотика сломана, но так оно упихивается.

    Код https://pastebin.com/4KUmwzb3

»
10 месяцев назад, # |
Rev. 3   Проголосовать: нравится +31 Проголосовать: не нравится

"B" можно было придумать с нуля, но легче читать блоги на CF почаще :)

https://mirror.codeforces.com/blog/entry/105723

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

F на (100?) баллов (если кому интересно). Изначально скажем $$$v = 0$$$ и сделаем форик $$$u$$$ in $$$1...n-1$$$. Если направление $$$vu$$$ $$$forward$$$, делаем $$$v := u$$$. Заметим, что для всех вершин кроме $$$v$$$ у нас есть ровно одно исходящее ребро, у $$$v$$$ их 0. Будем спрашивать направление до всех вершин от $$$v$$$, пока они не закончатся или пока у нас не станет 2 исходящих ребра. Далее, если 2 исходящих ребра нашлись, можно втупую за квадрат спросить все пары вершин, каждая из которых имеет 1 выходящее ребро. Так останутся 2 кандидата на ответ. Каждого спросим за $$$n - 1$$$ запрос. Итого $$$4n$$$ запросов. Почему $$$4n$$$? На момент, когда у нас осталось 2 кандидата, кол-во исходящих рёбер из всех остальных вершин ровно 2, поэтому мы сделали чуть меньше чем $$$2n$$$ запросов. Почему кандидатов будет 2? Если за квадрат спрашивать все вершины, каждая из которых ещё не имеет 2 исходящих ребра, может остаться не более 3 кандидатов, которые образуют цикл. Мы фориком сделали так, что любой цикл бы содержал вершину $$$v$$$, а потом её поспрашивали, поэтому кандидатов осталось 2

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

    Ну кстати F — IMO Short List 2019 C8, если кому интересно...

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

Сегодня появился официальный разбор и дорешка в тренировке на Codeforces.

By the way, моё решение в E не прошло последнюю группу по времени, зато F прошла на 100 из-за плохого интерактора :)

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

    Я слышал что у кого то прошла Е с СНМ со сжатием путей и откатами

    Редакт: Во блин, оказалось был не прав и всё нормально работает. Десять раз извиняюсь.

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

      Почему же не могут? Вполне себе могут, просто непонятно зачем

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

        Разве? Всегда считал (и слышал от других) что при использовании сжатия путей откаты не будут работать — ведь между откатами родитель вершинки может поменяться и как мы будем запоминать

        Только что осознал что все эти годы жил во лжи...

        Пы.Сы.

        на всякий случай уточню — откаты действительно работают вместе со сжатием не ломая асимптотики?

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

        Оказалось, действительно возможно

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

        Но за дезинформацию выше прошу прощения =)