Блог пользователя Mr.Temirbay

Автор Mr.Temirbay, 12 лет назад, По-русски

Всем добрых суток!

Сегодня на сайте neerc пройдет олимпиада.

Время проведения : click.

Предлагаю здесь обсудить задачи.
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

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

Всем удачи !

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

Как решать B и D?

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

Добавил в Codeforces::Тренировки 2012-2013 Цикл интернет-олимпиад. Шестая личная олимпиада (23 февраля 2013 года). Не могу не сказать "спасибо" членам жюри из ИТМО — архив контеста парсится легко, без каких-либо сложностей. Всю олимпиаду добавил минут за 10.

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

Расскажите пожалуйста, как B решать и D на сотню.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

    B. Динамика dp[x][y] — какое минимальное количество операций надо вставить так, чтобы у первого капитана были выполнены операции с нулевой по x — 1, а у второго — с нулевой по y — 1. Мы можем сделать либо x-ую операцию первого капитана, второй в это время пьет ром, либо y-ую операцию второго капитана, первый пьет ром, либо одновременно две операции.

    Осталось научиться проверять, что сделанная операция не будет пересекать состояние другого капитана. Ну, давайте для каждого i и j насчитаем, пересекает ли i-я операция состояние на j-й префикс операций другого капитана. Это делается деревом отрезков с присвоением на отрезке. Дальше понятно, как отвечать на запросы.

    Вот код, возможно, посмотрев на него, станет понятнее: http://pastebin.com/2zeWp4mQ

    D. У меня код получил на самой олимпиаде 80, но вообще-то локально и на Codeforces он проходит все тесты.

    У нас есть колесо. Будем называть все множество ребер, концом которых не является 0, колесом, а оставшиеся ребра — палками.

    Заметим, что всегда существует минимальный остов, в котором не участвует максимальное ребро на колесе. Удалим его. Теперь колесо — отрезок.

    Насчитаем динамику dp[v][2] — мы стоим на вершине v колеса, нолик или единичка при этом означают, соединена ли компонента связности, в которой сейчас вершина v, с нулевой вершиной. Переходы очевидны — соединяем вершину v с нулем или не соединяем, соединяем вершину v + 1 с нулем или не соединяем, соединяем вершину v + 1 с предыдущей или не соединяем. Получилось решение за O(Q * N).

    А теперь надо просто запихнуть эту динамику в дерево отрезков. В каждой вершине дерева будем хранить dist[2][2] — длину минимального перехода из одного состояния в другое. Теперь, чтобы сделать апдейт значения на ребре, нужно просто сделать апдейт в дереве отрезков. Получилось решение за O(N log N).

    Вот код: http://pastebin.com/fDECf5ZG

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

      А максимальное ребро? Оно ведь может изменится. Мне не совсем понятно как с этим быть? Можешь немного поподробней рассказать, если не сложно?

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

        Номер максимального ребра находится сетом :) Мы храним в дереве отрезков динамику для всех ребер. Динамика без максимального ребра = композиция динамик на двух отрезках.

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

          Это чертовски красивое решение. В последнее время достаточно много задач встречал на такую "динамическую динамику", но эта — самая веселая из них. Спасибо!

          Кстати, разве в общем виде она не решается с нормальной сложностью?