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

Opencup XIV. Гран-при Саратова.
Автор niyaznigmatul, 11 лет назад, По-русски

Сегодня прошел очередной этап Открытого кубка — Гран-при Саратова. Насколько я понимаю, на тех же задачах сегодня же прошел тур Петрозаводских сборов.

Монитор

Предлагается здесь обсудить задачи. Меня интересуют решения задач F и J.

Открытую ссылку на условия задач я не нашел. Если у вас есть логин для opencup в ejudge или Яндекс.Контест их можно найти.

UPD: Условия (англ)

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

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

Моё решение задачи F такое: Сначала сделал так чтобы все a[i] были меньше b[i]. Затем отсортируем так, чтобы все a[i] шли по возрастанию, а если a[i] равны у некоторых пар, то там b[i] должны идти по убыванию. После того как отсортировали первая пара ответа будет первой парой отсортированного массива: x[1]=a[1], y[1]=b[1]; Затем идём циклом от 2 до n и смотрим: Если пару a[i], b[i] можно поставить после последней найденной пары (a[i]>=x[last] && b[i]<=y[last]) то ставим, если же нельзя, то ставим в конец перевёрнутую пару x[n]=b[i], y[n]=a[i], когда в следующий раз найдём пару которую поставить нельзя, то ставим на место x[n-1] и y[n-1]. Как прошли все n шагов, то циклом проверяем если массив корректный, то выводим ответ, иначе no

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

    А как доказать что это правильно?

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

      После того как мы отсортировали массив в первый раз, то у нас все a[i] уже стоят корректно, как и просилось в условии, осталось только расставить чтобы и все b[i] удовлетворяли условию. Если на каком-то шаге мы не можем поставить, то единственное где может стоять это пара, то это в конце, после того как мы присвоим x[n]=b[i], y[n]=a[i], то y[i] будет всегда корректно, так как и a[i] были корректные, а b[i] переносится просто на место x[n], так как они неразрывная пара. Так мы построим единственный массив пар ответов, где все a[i] корректно стоят на своих местах, и теперь просто остаётся проверить, стоят ли все числа b[i] корректно на своих местах, если да, то мы построили, а если нет, то для того чтобы поставить все b[i] в корректность, то нам придётся поменять местами некоторые a[i], а это разобьёт корректность всех a[i], а значит и корректного варианта не существует.

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

J:

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

Понятно, что сумма в куче всегда уменьшается, поэтому возвращать какие-то элементы никогда не нужно. Единственный вопрос -- сколько нужно шоколадок, а это мы просто перебрали.

Там на макс-тесте (n = 106) где-то 2 * 107 таких замен происходит, поэтому можно тупо всё в куче поддерживать.

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

    Можно даже доказать что замен будет O(n log n) — у шоколадки с номером t будет не более (n-1) / (t + 1) + 1 элементов не превосходящих n, значит количество замен ограничено сверху n*H_{n+1} + O(n). (H_n — сумма первых n членов гармонического ряда).

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

    Я не понял. В структуре времена решения каждой задачи или времена решения отрезков задач?

    UPD: Ок. Объяснили. Храним времена решения каждой задачи. При добавлении шоколадки, несколько раз делаем так, если выгодно: удаляем самую дорогую (она является концом какого-то отрезка) и добавляем вместо нее следующую задачу в новый отрезок.

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

Как решалась B? Или почему падает такое:

Сделаем ответ равным (2n - 1) * 2. Количество ходов в обычной задаче про Ханойские башни умножить на два, так как вместо одного перемещение делаем два. Теперь если у в конечном положении надо поменять местами 2 равных диска местами, добавим к ответу (2i - 1) * 2 + 1, где i размер диска.

Если мы хотим поменять 2 диска одного размера, нам надо:

  1. передвинуть все диски меньшего размера в один стержень (2i - 1 операции)

  2. поставить 1 диск нужного размера

  3. передвинуть все диски меньшего размера на него (2i - 1 операции)

  4. поставить второй диск на место

  5. передвинуть все остальные диски в нужное место (шаги 1-3, (2i - 1) * 2 + 1 операции)

Итого сделаем (2i - 1) * 4 + 1 операции, отнимем от него (2i - 1) * 2 = разница операции для N-ного диска И получим наши (2i - 1) * 2 + 1

Мы можем сделать эти операции на ходу, из-за этого и разница.

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

    Поменять местами два нижних диска можно более эффективно:

    1. Переместить все диски меньшего размера на стержень 2.

    2. Переместить оба нижних диска на стержень 3.

    3. Переместить остальные диски на стержень 1.

    4. Переместить нижние диски на стержень 2.

    5. Переместить остальные диски на них.

    Ниже напишу авторское решение.

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

    Авторское решение по В:

    Посмотрим на два нижних диска. Если после перемещения они должны лежать в обратном порядке — мы можем выполнить перемещение за 2 + 2 * К операций, где К = K[n-1] — количество действий для перемещения остальной башни. Пока мы не думаем о порядке остальных дисков.

    Если два нижних диска должны идти в том же порядке, есть два варианта. 1) за 3 + 4 * К операций (с поочередным перемещением нижних дисков), 2) за 4 + 3 * К операций (с перемещением нижней пары на один колышек, потом — на другой, каждый раз меняя порядок).

    Вариант 1) выгоднее только если K = 0 (у нас всего одна пара дисков). Это не так очевидно, потому что при перемещении остальной башни у нас сохраняется порядок всех дисков, кроме двух нижних, который меняется на противоположный. Т.е. варианты 1 и 2 приводят к разным ситуациям в дальнейшем.

    Если следующая снизу пара дисков оказалась в неправильном порядке, то мы одно из перемещений остальной башни с ней будем выполнять не за 2 + 2 * K' операций, а по варианту 1 или 2 (К' — это количество действий на перемещение новой "остальной башни", т.е. башни из 2 * (n — 2) дисков) и т.д.

    Вариант 1 добавляет нам 1 + 2 * К операций, вариант 2 — (2 + К) операций, т.е. на К — 1 операцию меньше. Но после него может получиться так, что нужно будет менять местами все последующие пары. Это в худшем случае добавит sum[n-2] = (2 + K[n-2]) + (2 + K[n-3]) + ... + (2 + K[2]) + (2 + K[1]) + 1 операцию. Мы считаем, что дальше действуем по варианту 2 и при n = 1 по варианту 1. Если в оптимальном алгоритме и дальше есть действия по варианту 1, то выберем действие по варианту 1 для наименьшей башни и покажем, что вариант 2 будет оптимальнее. Ясно, что К[i] = 2 * K[i — 1] + 2, K[1] = 2. По индукции получаем sum[n-2] < K[n-1]. Таким образом, в случае использования варианта 1 мы сэкономим не более K[n-1] — 1 операции, но ровно настолько операций меньше мы выполним при варианте 2. Поэтому вариант 2 не хуже (а часто и лучше) варианта 1.

    Самый плохой тест — сохранение исходного порядка: 2*n, 2*n-1, 2*n-2, ..., 4, 3, 2, 1. Для него ответ 2^(n + 2) — 5. Это и есть задача и ответ из "Конкретной математики".

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

      1) за 3 + 4 * К операций (с поочередным перемещением нижних дисков), 2) за 4 + 3 * К операций (с перемещением нижней пары на один колышек, потом — на другой, каждый раз меняя порядок).
      Непонятно почему здесь везде одинаковое количество операций для перемещения остальной башни. Ведь возможно, что остальную башню выгодно перемещать в определённых порядках, то есть минимальное количество операций на каждом перемещении остальной башни не даёт минимального суммарного количества и жадность не работает. Тогда количество операций будет что-то типа 3 + K1, 1 + K1, 2 + K1, 3 + K1, 4 для первого варианта и 4 + K2, 1 + K2, 2 + K2, 3 для второго. И тогда непонятно сколько именно добавляют варианты 1 и 2.

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

        1. Можно показать, что если нам предстоит несколько перемещений остальной башни, то все проблемы внутри этой башни оптимально решать за одно перемещение (например, за последнее). Остальные перемещения выполняются за наименьшее возможное число операций (за К).

        2. Как это показать? Примерно так, что нижняя пара в остальной башне все равно не зависит от того, что выше. Чтобы поменять ее порядок, нужно просто перекинуть ее дополнительный раз (например, в конце). Аналогично рассуждаем для тех пар, которые выше.

        3. В моем решении приводится доказательство того, что даже если вариант 1 нам ничего не добавит, а в варианте 2 придется выполнять дополнительные ходы для каждой пары дисков, то вариант 2 не хуже. А это самый худший случай.

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

По поводу F. Есть точно такая же задача на тимусе: 1743. И предлагалась в Петрозаводске, летом 2009-го года.

→ Ответить