За свой небольшой опыт СП у меня в голове твёрдо сформулировался пласт алгоритмов, которые можно назвать "прикольными идеями".
Более формально — это такие алгоритмы, которые легко понимаемы, но не стоят в одном ряду с классическими алгоритмами, в первую очередь, из-за не совсем стандартного подхода. Более того, на них не так сильно сосредоточено внимание, так как им не имеет смысла уделять больше 5 лекционных минут.
Однако, в памяти от таких идей остался только линейный поиск 2го минимума(остальные, похоже, въелись в мышление и кажутся совсем натуральными). Хотелось бы систематизировать знания, так что пишите в комментах свои "прикольные идеи". Ещё может оказаться, что об этом уже написано, так что ссылки на такие публикации приветствуются.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | pajenegod | 145 |
| 9 | Petr | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 13.05.2024 20:23:23 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Первое, что пришло в голову:
А можно пожалуйста про 5-ый пункт поподробнее, или пример любой, а то я не знаю, кажется :(
Например, задача 150E - Замерзаем красиво. Там надо найти путь длины от L до R с максимальной медианой. Делаем бинпоиск, заменяем все рёбра с весом ≥ M на 1, остальные — на -1. После этого требуется проверить существование пути нужной длины неотрицательного веса.
Или вот такая задача: найдите в дереве путь длины L с максимальной k-й порядковой статистикой. Вроде решается точно так же: бинпоиск по ответу, заменяем рёбра меньшие на 1, остальные — на ноль, надо проверить, есть ли путь нужной длины с весом <k.
Приведите, пожалуйста, пример использования идеи из первого пункта или ссылку, где можно об этом почитать. Где-то об этом уже слышал, но теории так и не нашел, к сожалению.
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) * Σ) (второе слагаемое — предподсчёт, Σ — размер алфавита)
Спасибо за ответ, очень интересно. Подскажите, пожалуйста, можно ли про это еще где-нибудь почитать?
У нас в раунде была такая задача: 201D - Инновационно новая задача
Разбор
А можно подробнее про четвертый пункт? Не раз слышал сочетание "золотое сечение" вместе с бинарным/тернарным поиском, но ни разу не видел его использования. Зачем оно вообще нужно?
Можно делить не в отношении 1:1:1, а в отношении φ: 1: φ (или 1: φ: 1 надо порисовать). Тогда на следующем уровне одно из двух нужных значений уже будет посчитано.
Вот 2 интересные, на мой взгляд, идеи.
В задачах, где нужно хранить сеты с какой-то информацией о вершинах дерева (например, их цвета) и передавать их наверх, при объединении будем перекладывать элементы из меньшего по размеру сета в больший. Тогда решение работает за асимптотику O(NlogN), а не O(N2), как сперва кажется. Причина в том, что при каждом перекладывании элемента размер сета, в котором он хранится, увеличивается как минимум в 2 раза. Таким образом, каждый элемент будет переложен не более чем O(logN) раз. Примеры таких задач: задача F с Харьковской зимней школы 2012, 246E - Братья по крови возвращаются с недавнего CF раунда.
В задачах на строки недостаточно одного хэша по модулю порядка 109. Объясняется это парадоксом дней рождения — чтобы вероятность взломать хэш-функцию, принимающую N различных значений, превысила 50%, требуется порядка
случайных строк. Поскольку в качестве входных данных бывают строки длины до 106, то вероятность коллизии очень велика. Значит, нужно использовать хэширование по двум простым модулям.
Чуть-чуть поподробнее, с сетами.
Каждый элемент перекладывается log раз.
Добавление происходит за log.
Элементов n.
И того асимптотика n * (log ^ 2)
Так?
при вставке n отсортированных элементов возможна оптимизация, и получается амортизированная константа. Простейший пример:
-- 233 мс в запуске
-- 108 мс
Наверное, caustique имел в виду, что будет
O(N log N)перекладываний.Частенько в подобных задачах речь идёт о какой-нибудь динамике
D[v][i], гдеv— вершина, аi— какой-то параметр, ограниченный размером поддереваv(например, количество каких-нибудь выбранных вершин в поддереве, или что-нибудь подобное). В таком случае, если мы всё храним массивами и аккуратно следим за индексацией (есть ещё фанаты хранить значения динамики в деках/стеках/очередях), и будем приливать меньшее к большему, то будет честное O(N log N).А есть ещё забавный факт, что если
iограничен не количеством элементов в поддереве, а глубиной поддерева, то перекладываний вообще будет ровно линейное количество.А этот забавный факт как-то доказывается?
Нужно сказать, что время работы в вершине — это её глубина минус глубина самого глубокого сына. Это суммируется в линию.
1) Хеш как идея. Прямая индексация где-то рядом. Идея применения такой штуки не ограничивается сравнениями строк да хеш-таблицами. Применяется в распределенных и параллеьных вычислениях например, еще кое-где не буду спойлерить задумку задачи.
2) Структура данных с откатами. Поделали чего-то, поизменяли структуру выполнив O(k) действий, значит за время O(k) можно вернуть структуру в исходное состояние, выполнив её изменения в обратном порядке.
3) Персистентные структуры данных.
4) Разделяй-и-властвуй. применятся на каждом шагу, даже не замечая этого. тот-же бинпоиск можно сказать на этой идее сделан.
Как-то это слишком глобально :)
Вряд ли что-нибудь из этого можно за 5 минут понять, а на осознание уйдёт совсем куча времени
Чего, нормально. Как минимум пункт 2 подходит под тему.
Массив с очищением за O(1) или тегированный массив.
Объявляем:
Пользуемся:
Конечно, это примитивно, но тоже в каком-то роде идеи: 1) Считывание всего инпута и его обработка в удобном нам порядке. 2) Оффлайновый предпросчет (precalc) в задачах с малым количеством возможных инпутов за время, ограниченное продолжительностью контеста;) 3) Когда вещественные числа в инпуте заданы с фиксированной точностью, удобно их домножить на 10 в какой-то степени и работать с целыми.
В задачах с баллами иногда имеет смысл забивать ответы к некоторым тестам заранее. Если у таких задач сложный инпут, можно просто сравнивать его со своими тестами просто построчно, а потом переоткрыть input-файл и читать уже с парсингом.
А, а ещё идея "пошаффлим входные данные". Так, например, можно найти минимальную покрывающую точки окружность за линию.
Можно поподробнее, что такое "пошаффлим"? Объясните, пожалуйста, эту идею на примере упомянутой задачи.
Пошаффлим = случайно перемешаем. Собственно, как решать задачу про минимальную покрывающую окружность: Мы будем по очереди добавлять точки и смотреть, как меняется окружность. Иначе говоря, у нас уже есть N точек, для них мы знаем минимальную окружность, добавляем N+1 точку. Если она лежит внутри окружности -- всё здорово, переходим к следующей. Если вне -- нужно перестраивать ответ.
Итак, получили как будто бы кубическое решение. Но ведь мы умные и перемешали ввод, так что теперь давайте считать матожидание.
Линия!
Можете пояснить третий пункт? Вот мы на каком-то этапе знаем, что окружность проходит через две точки, причём через одну наверняка (это наша номер N+1), а через вторую предположительно. Потом мы в ходе просмотра оставшихся точек находим третью, которая в текущую окружность не влазит. Как мы тогда проводим новую текущую окружность — через две точки или через три? И если через три, то как мы в следующий раз будем решать, какую выбрасывать?
Не, не так. Пусть мы в пункте 2 нашли точку, не попадающую в окружность -- тогда она тоже наверняка лежит на окружности для точек (1..N+1). И теперь нам осталось только найти только третью точку. Для этого пробежим по всем оставшимся точкам, и если точка вылезает за окружность -- заменяем третью точку на неё. И да, я это подробно не расписывал, но на протяжении всей программы нужно аккуратно смотреть -- текущая окружность построена на двух точках или трёх.
Но в пункте 2 мы же изначально построили окружность на двух точках — N+1 (которая точно нужна) и 1 (которую взяли случайно). Если мы после этого возьмём произвольную точку, которая не попадает в окружность, построенную на этих двух, то вовсе не факт, что она "тоже наверняка лежит на окружности для точек (1..N+1)".
Как ни странно, факт :) Попробуй представить себе заведомо большую окружность, а потом начни её мысленно сжимать, пока она не упрётся о наши точки.
Да я всё пытаюсь намекнуть, что на самом деле дела тут ещё хуже. Если у нас одна точка (N+1) хорошая, а вторая (1) произвольная, то даже если мы через них проведём окружность бесконечно большого радиуса, то не факт, что она будет содержать все точки.
Последний раз. хорошо? Каждый раз, когда мы на любом шаге начинаем перебирать точки, текущая окружность будет текущим ответом для всех точек до текущей и фиксированных точках на предыдущих шагах.
То есть она, конечено, не произвольная должна быть. Мы их по очереди перебираем и смотрим, влезает точка в текущую окружность или нет. Не влезает — точка — текущий ответ.
Уж и не знаю насколько идея интересна, может это вообще классика, хоть скажете тогда как это называется) В одной задаче требовалось найти наибольшую возможную длину пути по графу, у которого все ветки одинаковой длины. Циклов нет. Вообще задачка школьная, со смешными ограничениями. У нас кто решил просто делали dfs из всех вершин. Я тогда про dfs и не слышал. Думал наверное неделю, дошло — надо проходить по списку вершин и удалять те, у которых есть только одна связь. Так делать пока в списке не останется одна или ноль вершин. Теперь смотрим сколько раз нам удалось пройтись, пусть N раз. Если вершина осталась одна, ответ 2*N. Если не осталось — 2*N + 1. Помнится очень гордился своей придумкой) Вообще идея пришла когда я себе представил граф в виде гаек, связанных ниточками. Вот взял я кучу гаек, связал, запутал как мог. И где теперь решение? Вот оно, от этой гайки до этой. По пальцу в них суешь и растягиваешь. Все несущественные "отростки" как бы обвисают на этой самой длинной "прямой". Вот хорошо бы их убрать как-то. Заметил, что из самой дальней гайки "отростка" до ближайшей гайки "прямой" можно добраться никак не быстрее, чем из ближайшей крайней гайки этой "прямой". Начал представлять по шагам, как иду от края отростка и от края прямой одновременно. Ну и тут собственно пришла идея что надо их удалять, а не идти по ним. Последнюю часть написал чисто чтобы было проще таким как я)
Примерно понял почему этот алгоритм правильно работает. Похоже что этот алгоритм еще можно распараллелить, удаляя вершины с помощью N потоков.
Может сдадите да мне решение скинете? Очень уж интересно, как это будет выглядеть. Ни разу решения "с потоками" не видел) Но точно могу сказать что этот алгоритм получил АС, пусть даже и не в самой лучшей реализации. Ну или даже в самой худшей.
А кто-нибудь может рассказать, что за идея подразумевается под упомянутым в этом блоге "линейным поиском 2го минимума"?
Я думаю идея такая: мы храним две переменные min и min2. Для каждого входного числа(t) проверяем условия
Соответственно min2 это и будет второй минимум.
Ясно, я-то думал, что есть какой-то тип задач, как-то решающийся с использованием второго минимума.
Нахождение решения динамики по двум параметрам используя линейный размер памяти (когда нам нужна только строчка чтобы посчитать следующую строку в матрице динамики, но мы хотим еще и путь восстановить потом). Потоки с использованием бинарного поиска и асимптотика такого алгоритма.
Я однажды решал на cf сложную задачу, но у меня не получалось. Тогда я использовал прикольную идею: я скопировал код tourist, и получил АС.