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

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

За свой небольшой опыт СП у меня в голове твёрдо сформулировался пласт алгоритмов, которые можно назвать "прикольными идеями".
Более формально — это такие алгоритмы, которые легко понимаемы, но не стоят в одном ряду с классическими алгоритмами, в первую очередь, из-за не совсем стандартного подхода. Более того, на них не так сильно сосредоточено внимание, так как им не имеет смысла уделять больше 5 лекционных минут.
Однако, в памяти от таких идей остался только линейный поиск 2го минимума(остальные, похоже, въелись в мышление и кажутся совсем натуральными). Хотелось бы систематизировать знания, так что пишите в комментах свои "прикольные идеи". Ещё может оказаться, что об этом уже написано, так что ссылки на такие публикации приветствуются.

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

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

Первое, что пришло в голову:

  1. Поменять местами параметр и результат в какой-нибудь динамике
  2. Применить афинное преобразование ко входным данным, чтобы убить дурацкие углы
  3. Преобразование динамики в возведение матрицы в степень
  4. Тернарный поиск с золотым сечением
  5. Поиск k-й порядковой статистики (или медианы) на какой-нибудь фигне при помощи бинарного поиска и заменой чисел на 0/1(/-1)
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    А можно пожалуйста про 5-ый пункт поподробнее, или пример любой, а то я не знаю, кажется :(

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

      Например, задача 150E - Замерзаем красиво. Там надо найти путь длины от L до R с максимальной медианой. Делаем бинпоиск, заменяем все рёбра с весом  ≥ M на 1, остальные — на -1. После этого требуется проверить существование пути нужной длины неотрицательного веса.

      Или вот такая задача: найдите в дереве путь длины L с максимальной k-й порядковой статистикой. Вроде решается точно так же: бинпоиск по ответу, заменяем рёбра меньшие на 1, остальные — на ноль, надо проверить, есть ли путь нужной длины с весом <k.

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

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

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

      176D - Гипер Строка. Вначале смотрим на простую квадратнуюю динамику d[i][j]=ans (i ≤ 2·109, j ≤ 2000 — при данных i и j максимальный ответ. Меняем местами i и ans (ans ≤ 2000) — d[ans][j]=i — при данных j и ans минимальная позиция i, в которой такое возможно.

      Итого получили приемлимое количество состояний (4·106). Переход довольно простой — найти следующий символ X после позиции i в гиперстроке, это делается предподсчётом по всем базовым строкам.

      В частности, мы получили алгоритм поиска наибольшей общей подпоследовательности за O(min(n, m)2 + max(n, m) * Σ) (второе слагаемое — предподсчёт, Σ — размер алфавита)

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

    А можно подробнее про четвертый пункт? Не раз слышал сочетание "золотое сечение" вместе с бинарным/тернарным поиском, но ни разу не видел его использования. Зачем оно вообще нужно?

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

      Можно делить не в отношении 1:1:1, а в отношении φ: 1: φ (или 1: φ: 1 надо порисовать). Тогда на следующем уровне одно из двух нужных значений уже будет посчитано.

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

Вот 2 интересные, на мой взгляд, идеи.

  1. В задачах, где нужно хранить сеты с какой-то информацией о вершинах дерева (например, их цвета) и передавать их наверх, при объединении будем перекладывать элементы из меньшего по размеру сета в больший. Тогда решение работает за асимптотику O(NlogN), а не O(N2), как сперва кажется. Причина в том, что при каждом перекладывании элемента размер сета, в котором он хранится, увеличивается как минимум в 2 раза. Таким образом, каждый элемент будет переложен не более чем O(logN) раз. Примеры таких задач: задача F с Харьковской зимней школы 2012, 246E - Братья по крови возвращаются с недавнего CF раунда.

  2. В задачах на строки недостаточно одного хэша по модулю порядка 109. Объясняется это парадоксом дней рождения — чтобы вероятность взломать хэш-функцию, принимающую N различных значений, превысила 50%, требуется порядка случайных строк. Поскольку в качестве входных данных бывают строки длины до 106, то вероятность коллизии очень велика. Значит, нужно использовать хэширование по двум простым модулям.

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

    Чуть-чуть поподробнее, с сетами.

    Каждый элемент перекладывается log раз.

    Добавление происходит за log.

    Элементов n.

    И того асимптотика n * (log ^ 2)

    Так?

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

      Добавление происходит за log

      при вставке n отсортированных элементов возможна оптимизация, и получается амортизированная константа. Простейший пример:

      set<int> a;
      for(int i=0; i<1000000;++i) a.insert(i);
      

      -- 233 мс в запуске

      set<int> a;
      set<int>::iterator it = a.begin();
      for(int i=0; i<1000000;++i) it=a.insert(it,i);
      

      -- 108 мс

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

      Наверное, caustique имел в виду, что будет O(N log N) перекладываний.

      Частенько в подобных задачах речь идёт о какой-нибудь динамике D[v][i], где v — вершина, а i — какой-то параметр, ограниченный размером поддерева v (например, количество каких-нибудь выбранных вершин в поддереве, или что-нибудь подобное). В таком случае, если мы всё храним массивами и аккуратно следим за индексацией (есть ещё фанаты хранить значения динамики в деках/стеках/очередях), и будем приливать меньшее к большему, то будет честное O(N log N).

      А есть ещё забавный факт, что если i ограничен не количеством элементов в поддереве, а глубиной поддерева, то перекладываний вообще будет ровно линейное количество.

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

        А этот забавный факт как-то доказывается?

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

          Нужно сказать, что время работы в вершине — это её глубина минус глубина самого глубокого сына. Это суммируется в линию.

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

1) Хеш как идея. Прямая индексация где-то рядом. Идея применения такой штуки не ограничивается сравнениями строк да хеш-таблицами. Применяется в распределенных и параллеьных вычислениях например, еще кое-где не буду спойлерить задумку задачи.
2) Структура данных с откатами. Поделали чего-то, поизменяли структуру выполнив O(k) действий, значит за время O(k) можно вернуть структуру в исходное состояние, выполнив её изменения в обратном порядке.
3) Персистентные структуры данных.
4) Разделяй-и-властвуй. применятся на каждом шагу, даже не замечая этого. тот-же бинпоиск можно сказать на этой идее сделан.

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

    Как-то это слишком глобально :)
    Вряд ли что-нибудь из этого можно за 5 минут понять, а на осознание уйдёт совсем куча времени

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

      Чего, нормально. Как минимум пункт 2 подходит под тему.

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

Массив с очищением за O(1) или тегированный массив.

Объявляем:

  • Обычный массив
  • Массив, где для каждого элемента исходного массива будет храниться время изменения (массивы можно слить в один, используя структуры или записи)
  • Переменную текущего времени

Пользуемся:

  • При обращении к элементу сравниваем текущее время с временем изменения элемента. Если текущее время больше, значит, данные устарели, и мы считаем, что в ячейке 0 (или то, что играет роль нуля в задаче), иначе всё как обычно.
  • Изменяя элемент, мы изменяем время этого элемента на текущее.
  • Чтобы очистить весь массив, увеличиваем текущее время.
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится
  1. Meet-in-the-middle. Например, задача о рюкзаке решается этим приёмом за O(2n / 2 * n). При этом используется метод 2
  2. Метод двух указателей
»
12 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Конечно, это примитивно, но тоже в каком-то роде идеи: 1) Считывание всего инпута и его обработка в удобном нам порядке. 2) Оффлайновый предпросчет (precalc) в задачах с малым количеством возможных инпутов за время, ограниченное продолжительностью контеста;) 3) Когда вещественные числа в инпуте заданы с фиксированной точностью, удобно их домножить на 10 в какой-то степени и работать с целыми.

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

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

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

А, а ещё идея "пошаффлим входные данные". Так, например, можно найти минимальную покрывающую точки окружность за линию.

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

    Можно поподробнее, что такое "пошаффлим"? Объясните, пожалуйста, эту идею на примере упомянутой задачи.

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

      Пошаффлим = случайно перемешаем. Собственно, как решать задачу про минимальную покрывающую окружность: Мы будем по очереди добавлять точки и смотреть, как меняется окружность. Иначе говоря, у нас уже есть N точек, для них мы знаем минимальную окружность, добавляем N+1 точку. Если она лежит внутри окружности -- всё здорово, переходим к следующей. Если вне -- нужно перестраивать ответ.

      1. Ясно, что новая окружность будет проходить через эту "плохую" (N+1) точку. Осталось найти ещё две (или одну, так как окружность может строиться на диаметре).
      2. Построим окружность на диаметре точка 1 — точка (N+1). Теперь опять по очереди добавляем точки. Если очередная точка лежит внутри окружности -- всё хорошо. Если нет -- переходим к пункту 3 :)
      3. Итак, у нас вылезла за окружность ещё одна точка -- значит теперь минимальная покрывающая окружность проходит через эти две точки. Опять перебираем оставшиеся точки. Если очередная точка влезает в окружность -- всё хорошо. Если же нет -- значит окружность проходит через неё, обновляем ответ.

      Итак, получили как будто бы кубическое решение. Но ведь мы умные и перемешали ввод, так что теперь давайте считать матожидание.

      P(N) -- Время выполнения шага 1 с подшагами
      Q(N) -- Время выполнения шага 2 с подшагами
      R(N) -- Время выполнения шага 3 с подшагами
      
      P(N) = P(N-1) + 3/N * Q(N) // 3/N -- вероятность того, что точка лежит на окружности
      Q(N) = Q(N-1) + 2/N * R(N) // 2/N -- вероятность того, что одна из оставшихся точек лежит на окружности
      R(N) = O(N)
      
      Q(N) = Q(N-1) + O(1)
      Q(N) = O(N)
      P = P(N-1) + O(1)
      P(N) = O(N)
      

      Линия!

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

        Можете пояснить третий пункт? Вот мы на каком-то этапе знаем, что окружность проходит через две точки, причём через одну наверняка (это наша номер N+1), а через вторую предположительно. Потом мы в ходе просмотра оставшихся точек находим третью, которая в текущую окружность не влазит. Как мы тогда проводим новую текущую окружность — через две точки или через три? И если через три, то как мы в следующий раз будем решать, какую выбрасывать?

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

          Не, не так. Пусть мы в пункте 2 нашли точку, не попадающую в окружность -- тогда она тоже наверняка лежит на окружности для точек (1..N+1). И теперь нам осталось только найти только третью точку. Для этого пробежим по всем оставшимся точкам, и если точка вылезает за окружность -- заменяем третью точку на неё. И да, я это подробно не расписывал, но на протяжении всей программы нужно аккуратно смотреть -- текущая окружность построена на двух точках или трёх.

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

            Но в пункте 2 мы же изначально построили окружность на двух точках — N+1 (которая точно нужна) и 1 (которую взяли случайно). Если мы после этого возьмём произвольную точку, которая не попадает в окружность, построенную на этих двух, то вовсе не факт, что она "тоже наверняка лежит на окружности для точек (1..N+1)".

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

              Как ни странно, факт :) Попробуй представить себе заведомо большую окружность, а потом начни её мысленно сжимать, пока она не упрётся о наши точки.

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

                Да я всё пытаюсь намекнуть, что на самом деле дела тут ещё хуже. Если у нас одна точка (N+1) хорошая, а вторая (1) произвольная, то даже если мы через них проведём окружность бесконечно большого радиуса, то не факт, что она будет содержать все точки.

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

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

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

              То есть она, конечено, не произвольная должна быть. Мы их по очереди перебираем и смотрим, влезает точка в текущую окружность или нет. Не влезает — точка — текущий ответ.

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

Уж и не знаю насколько идея интересна, может это вообще классика, хоть скажете тогда как это называется) В одной задаче требовалось найти наибольшую возможную длину пути по графу, у которого все ветки одинаковой длины. Циклов нет. Вообще задачка школьная, со смешными ограничениями. У нас кто решил просто делали dfs из всех вершин. Я тогда про dfs и не слышал. Думал наверное неделю, дошло — надо проходить по списку вершин и удалять те, у которых есть только одна связь. Так делать пока в списке не останется одна или ноль вершин. Теперь смотрим сколько раз нам удалось пройтись, пусть N раз. Если вершина осталась одна, ответ 2*N. Если не осталось — 2*N + 1. Помнится очень гордился своей придумкой) Вообще идея пришла когда я себе представил граф в виде гаек, связанных ниточками. Вот взял я кучу гаек, связал, запутал как мог. И где теперь решение? Вот оно, от этой гайки до этой. По пальцу в них суешь и растягиваешь. Все несущественные "отростки" как бы обвисают на этой самой длинной "прямой". Вот хорошо бы их убрать как-то. Заметил, что из самой дальней гайки "отростка" до ближайшей гайки "прямой" можно добраться никак не быстрее, чем из ближайшей крайней гайки этой "прямой". Начал представлять по шагам, как иду от края отростка и от края прямой одновременно. Ну и тут собственно пришла идея что надо их удалять, а не идти по ним. Последнюю часть написал чисто чтобы было проще таким как я)

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

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

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

А кто-нибудь может рассказать, что за идея подразумевается под упомянутым в этом блоге "линейным поиском 2го минимума"?

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

    Я думаю идея такая: мы храним две переменные min и min2. Для каждого входного числа(t) проверяем условия

    if(t<=min)
        min2=min, min=t;
    else if(t<min2)
        min2=t;
    

    Соответственно min2 это и будет второй минимум.

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

      Ясно, я-то думал, что есть какой-то тип задач, как-то решающийся с использованием второго минимума.

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

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

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

Я однажды решал на cf сложную задачу, но у меня не получалось. Тогда я использовал прикольную идею: я скопировал код tourist, и получил АС.