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

Автор Egor, 14 лет назад, По-русски
Лучше поздно чем никогда
Сегодня, 30 ноября, состоялся очередной СРМ
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Они, случайно, не перепутали задачи 500 див1 и 1000 див2?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как решать див2 1000? У меня на ум приходит только хэширование всех состояний и бфс. Ну и отсечения делать по-возможности.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Скорее всего венгерский алгоритм (ну или парасочетание с помощью минкоста).

      Каждой фигуре из начального состояния соответствует какая-то фигура из конечного. таким образом для каждой пары фигур можно определить сколько понадобится ходов для перехода.

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

        А что делать, когда все кони уже стоят на своих местах, но их надо подвинуть, чтобы пропустить пешку?

        Пример 1:

        ...

        .N.

        .P.


        ---


        .P..

        .N.

        ...


        Пример 2:


        ..P.P..
        .P...P.
        ...N...
        .P.P.P.
        ..P.N..
        .......

        -------

        ..P.P..
        .P.P.P.
        ...N...
        .P...P.
        ..P.N..
        .......


        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          "Moreover, a square may contain more than one piece."
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Спасибо. Я условие только мельком читал, думал там обычные шахматные правила.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я вот тоже думаю как решать. Оценка сверху количества позиций не такая и хорошая: 

      Но может решение и есть простой бфс, это же див2 всё-таки.

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Всего 20 фигурок. Задача на минимальный по стоимости парасоч, можно решить венгерским или мин костом, но это для изврата, динамика 20 * (2 ^ 20) (маску обработанных справа, количество обработанных слева) лучше подходит.
14 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
Поздравляю с победой!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решается див1 1000?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Вот мой код
    Если возникнут вопросы - you are welcome
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Во всех решениях этой задачи я увидел ДП по номеру добавляемого дерева ( в порядке убывания радиуса ), еще одному параметру и собственно получаемой длине. Вот этот загадочный параметр, я так понял, что это что-то типа количество пар среди уже вставленных, между которыми нельзя вставлять новые деревья. Есть ли какая-то более простая интерпретация и правильно ли я понял? 
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Скорее это количество мест, куда еще можно вставить дерево (при этом несколько подряд идущих мы считаем за одно)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Так в итоге, что является состоянием динамики? 
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Для каждой вершинки в порядке возрастания r надо определиться: либо соседние будут с большим индексом, либо одна из соседних уже есть, и тогда их можно "объединить" в одну вершинку, либо обе соседних уже в наличие, придётся объединять три вершины.
        Параметры: номер обрабатываемой вершинки, текущая сумма длин внутри объединенных вершин, текущее количество объединенных вершин.
  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится
    Отсутствовал вторую половину SRM, 1000 сдал сейчас на практисе.

    Отсортируем деревья по возрастанию r.
    Представим что перестановка это такой граф-цикл из N+1 вершины. Чтобы получить по графу перестановку надо разрезать цикл по N+1-ой вершинке. Вес ребра i-j в графе это rmax(i, j)
    Представим себе следующий разрез: вершины с 1 по i в одной части, i + 1 по N в другой.  Пусть через этот разрез проходит s пар рёбер. Будем считать число вариантов соединений в левой части разреза.

    Три параметра: i - текущая вершинка которую мы переносим через разрез, s - сколько пар рёбер есть в разрезе (проходит из одной части в другую), w - текущая длина перестановки, если учесть все рёбра между вершинами 1..(i - 1).
    Значение - количество графов оказывающихся в "левой" части разреза.

    Внутри надо перебрать сколько рёбер ведёт из вершины i налево, а сколько направо. Варианты:
    2-0 : таких вариантов s * (s - 1) * 2, при этом s надо уменьшать на 1. Вес увеличивается на 2ri
    1-1 : таких вариантов ровно s, при этом s не меняется. Вес увеличивается на ri
    0-2 : вариант один, s увеличивается на 1.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      не очень понятно, что значит "перестановка это граф-цикл из n+1 вершин". имеется ввиду набор циклов или что то другое? сколько элементов в перестановке n+1, если нет зачем фиктивная вершина? 
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Фиктивная нужна чтобы не вводить ещё два параметра - были ли конечные вершины цепи и есть ли сейчас от них отводы идущие через разрез. А так генерим все циклы и разрезаем их.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      еще хотелось бы спросить, как получается ответ на задачу?
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Мы будем знать сколько перестановок деревьев можно разместить на W лунках для каждого W. Ответ это сумма по W всех количеств, помноженных на биноминальные коэфициенты (надо вставить оставшиеся D-W лунок в N+1 место между деревьями)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Угу... теперь всё стало окончательно понятно, большое спасибо за разбор)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Наверное имелось ввиду: Значение - количество заданных состоянием перестановок.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В тройке не хватает только Petr'а =)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почему в 1000(див.2) в первом примере ответ -1. Ведь пешка может дойти до самого верха, стать конём, пойти вниз.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В примере № 1 (если речь идет о нем) требуется, чтобы на первой строке оказалась именно пешка, а не конь.