(так как у меня нет подписчиков, этот пост, вероятно, просмотрит мало людей, так что если ты наткнёшься на него спустя месяцы/годы — да, ещё актуально)

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

Мои текущие знания для контекста

Пере-открыл сам:

(вещи, которые я придумал до того, как прочитал/был-ознакомлен о них)

• Полиномиальные хэши строк
• Выпуклая оболочка
• Персистентные структуры данных, такие как деревья (благодаря знакомству с функциональным программированием, иммутабельностью и т.п.)
• Min-span tree графа

Хорошо знаю:

• Различные графовые алгоритмы
• Различные деревья
• Дерево отрезков
• Префиксная функция, Алгоритм Ахо-Корасик
• Динамическое программирование
• Система непересекающихся множеств
• Парсинг с помощью рекурсии

Помню в общих деталях:

• Суффиксный массив

Запрогал хотя бы раз, но не разбирался глубоко и забыл:

• Min/max поток графа
• Суффиксный автомат
• Структура данных, подобная дереву отрезков, которая может выполнять только часть операций, но имеет меньшую константу и меньшее потребление памяти (не помню название)

Это не полный список того, что я знаю, но, надеюсь, он даёт общее представление, что я, скорее всего, не знаю, и что мне покажется интересным.

В идеале ищу:

• Ссылки на задач(у/и) CodeForces
• Название алгоритма/структуры данных, необходимой для её решения (информация, которую я постараюсь не использовать/гуглить, прежде чем решить самостоятельно)
• Ориентировочная сложность пере-изобретения данного алгоритма и решения соответствующей задач(и)