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

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

Здравствуйте дамы и господа. У меня не получается решить вот эту задачу 306B - Оптимизатор и то не в первый раз. В тегах написано ,то что это задача на жадный алгоритм , но как их решать — я не знаю. Объясните , пожалуйста , как решаются задачи такого рода ? Заранее благодарен.

UPD: Всем огромное спасибо за ваши идей , объяснения и внимание. Задача решена!

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

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

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

Как решать задачу, пока не придумал.

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

Жадный алгоритм — применяем на каждом шаге оптимальное решение по некоторому критерию. Навскидку, не знаю верно или нет — сортируем отрезки по возрастанию li (конца отрезка), бежим по всем отрезкам, и каждый раз когда можно отрезок удалить согласно условиям — удаляем.

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

    Хватанёте лишнего, например, в случае
    3
    1 4
    2 4
    3 4

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

      Нет. Не хватану. :) Будут убраны отрезки 3,2..4,3..4 Удаление второго не пройдет по ограничениям.

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

        Товарищ, вообще-то здесь надо удалить один отрезок — второй. Это три отрезка длины 4.

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

          Нужно выбросить максимальное количество команд, а не оставить. Я и привожу алгоритм выбрасывания максимального количества команд — трех команд.

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

            Здесь максимальное количество команд, которые можно выбросить — одна. А именно, вторая.

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

              Вторая команда покрывает все значения. Выбросить максимально можно три команды — все кроме второй. "Задача оптимизатора программы Поликарпа — выбросить максимальное количество инструкций из его программы так, чтобы оставшиеся инструкции установили значение 13 в тех и только тех байтах памяти, что и программа до оптимизации."

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

                Товарищ, читайте условие. 3 — это n, количество инструкций. Далее следуют три (!) инструкции, каждая из них имеет ДЛИНУ четыре, и начинаются они в точках 1, 2 и 3.

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

                  Да, спасибо. Я старый уже, читаю невнимательно :)

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

        Только проверка перебором не войдет в ограничения. Нужно например дерево отрезков на минимум.

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

          Пройдёт, ведь каждый отрезок мы переберём один раз.

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

            То есть решаем задачу от обратного, выбираем какие оставить?

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

              Изначально в моём решении все отрезки в статуе "непросмотрены". Потом каждый из них приобретает статус "взят" или "выброшен".

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

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

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

А, понял.

  1. Если есть несколько инструкций с одинаковым a_i, то оставляем только ту, у которой наибольшее l_i.
  2. Сортируем инструкции по возрастанию a_i.
    3.
    Дальше будем перебирать все инструкции по порядку, и каждую брать или отклонять. Для начала берём самую первую нерассмотренную инструкцию (изначально это просто самая первая). И запоминаем, что мы обеспечили заполнение памяти до места pos = a_i + l_i.
    4.
    a. Если ещё есть инструкции, у которых a_j <= pos, то перебираем их всех и оставляем ту, у которой a_j+l_j максимально. Её добавляем в отмет, остальные отбрасываем, обновляем pos = a_j+l_j. Снова переходим к пункту 4.
    b. Если таких инструкций нет, то забываем pos и переходим к пункту 3.
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Удобно писать подобное с помощью стека, если правая граница текущего отрезка больше чем текущая правая граница, то закинем в стек(предварительно POP-ая отрезок на вершине стека, пока этот отрезок лежит в объединении добавленного отрезка и предпоследнего отрезка в стеке), иначе игнорим его. Несложно показать, что это находит оптимальное решение. 3722543

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

Рассмотрим самую левую из всех покрытых точек L. Естественно, это точка является началом какого-то отрезка, и для того чтобы ее покрыть нужно включить в ответ какой-либо из отрезков, начинающихся в этой точке. Очевидно, что выгоднее всего будет выбрать тот из них, который имеет наибольшую длину. Пусть мы выбрали отрезок [L,R]. Тогда все отрезки, целиком в него входящие, можно выбросить за ненадобностью, а отрезки [L1,R1] имеющие с ним пересечение (т.е. L < L1 < R < R1) урезать до [R,R1]. После этого получаем ту же задачу с меньшим числом отрезков и самой левой точкой >= R. Продолжаем применять описанную процедуру пока не покроем все интервалы.

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

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

http://codeforces.me/contest/306/submission/3720123 Извиняюсь что код не отформатирован.

Сортируем все отрезки в порядке возрастания начальной ячейки. И в цикле - пропускаем все которые заканчиваются на уже покрытом отрезке. Для первого которые выходит за покрытый отрезок смотрим начало. Если оно дальше чем уже покрытый отрезок, то за точку старта берем его. Если не дальше, то за точку старта берем ячейку сразу за уже покрытым отрезком. Перебираем все команды начало которых не дальше чем точка старта, и выбираем среди них тот, который заканчивается дальше. и т.д. Решается в один проход, за O(m) Информация о n, и сбор данных о покрытых ячейках — в решении не нужно.

UPD. общая сложность (m*log m), за счет сортировки массива команд.

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

    Покрытый отрезок — последний покрытый отрезок. Отрезок, который покрывает последняя оставленная команда.

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

Моё решение таково: Представим каждую команду как скобки (). Левая скобка — a[i], правая скобка — a[i]+l[i]-1.
1) Уберём все скобки, которые вложены в другие.
2) Заведём массив длины n, элементы которого будут хранить количество скобок, которые "покрывают" этот элемент.
3) Скобки, которые покрывают элементы, в которых записана единица, являются "нужными" — их удалить нельзя.
4) Остались скобки, которые не "покрывают" единицы. Понятно, что эти скобки лежат на пересечении с "нужными". Поступим жадно. Уберём все скобки, кроме нужных. Будем пытаться "заделать" пустое пространство между ними наиболее длинными скобками. Пометим эти наиболее длинные скобки как "нужные".
5) Все скобки кроме нужных — есть ответ.
Длинно, некрасиво, но думаю такое решение имеет место быть.