(так как у меня нет подписчиков, этот пост, вероятно, просмотрит мало людей, так что если ты наткнёшься на него спустя месяцы/годы — да, ещё актуально)
Я ищу классные алгоритмы или структуры данных, которые любопытны, хитроумны и интересны, но при этом не запредельно сложны, так чтобы их можно было заново пере-изобрести самому при решении какой-то задачи.
Мои текущие знания для контекста
Пере-открыл сам:
(вещи, которые я придумал до того, как прочитал/был-ознакомлен о них)
- Полиномиальные хэши строк
- Выпуклая оболочка
- Персистентные структуры данных, такие как деревья (благодаря знакомству с функциональным программированием, иммутабельностью и т.п.)
- Min-span tree графа
Хорошо знаю:
- Различные графовые алгоритмы
- Различные деревья
- Дерево отрезков
- Префиксная функция, Алгоритм Ахо-Корасик
- Динамическое программирование
- Система непересекающихся множеств
- Парсинг с помощью рекурсии
Помню в общих деталях:
- Суффиксный массив
Запрогал хотя бы раз, но не разбирался глубоко и забыл:
- Min/max поток графа
- Суффиксный автомат
- Структура данных, подобная дереву отрезков, которая может выполнять только часть операций, но имеет меньшую константу и меньшее потребление памяти (не помню название)
Это не полный список того, что я знаю, но, надеюсь, он даёт общее представление, что я, скорее всего, не знаю, и что мне покажется интересным.
В идеале ищу:
- Ссылки на задач(у/и) CodeForces
- Название алгоритма/структуры данных, необходимой для её решения (информация, которую я постараюсь не использовать/гуглить, прежде чем решить самостоятельно)
- Ориентировочная сложность пере-изобретения данного алгоритма и решения соответствующей задач(и)
https://codeforces.me/problemset/problem/1949/B
Try to solve this in a time complexity that is not $$$O(n^2)$$$ or beyond. With this, you would reinvent:
Hall's theorem which I find very beautiful.
Pardon me if I failed to meet your constraints due to my inexperience.
Thanks for the suggestion!
Wouldn't a simple min(sort(aa) — sort(bb)) work? Ha-ha-ha. That would be too easy, and they'd certainly make n>=200 000 in such a case.
I'll think
Hehe, that's not it :). The solution is something way cooler !
Not codeforces, but I like this problem a lot. It is in romanian but translation should be relatively simple. Try to do it in $$$O(N)$$$.
Problem
but translation should be relatively simpleThen translate it, what's the problem?
The problem gives you a tree. A node is either a know-all that can answer queries or a know-nothing and has to ask one of its ancestors for the answer to the query. Each know-nothing might have a different ancestor they need to ask (for each node there is a $$$k$$$ that specifies that you should ask the $$$k$$$-th ancestor).
The task is to find for each node how many jumps a query makes (starting from that node) until it is answered.
The real issue is finding the k-th ancestor for each node in constant time.
Micro macro tree.
?
That's the solution to the 'The actual interesting part'.
I don't know what a micro macro tree is (although, I would not mind an explanation/resource).
Use a stack-like list.
Do a dfs from the root.
When entering a node add it to the end of the list. When exiting remove it from the list.
A node at depth $$$d$$$ with query of $$$k$$$ must look in the list at position $$$d-k$$$.
All the operations can be simulated on a
std::vectorfor example.The reason this is possible is that we solve the problem offline. If you were asked on the spot then this would not be doable (although maybe some persistent vector could work but at that point just use binary lifting)
https://cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf
Aliens' trick (the one that appeared in IOI16_aliens specifically). Do APIO10_commando first. Only person who managed to came up with that blind in-contest was LiTi ([user:jvcb] is only in-contest AC, but that was because he've known about the trick before)
Kruskal Reconstruction Tree/ Reachability Tree (online solution to that "How many nodes can be reached form node X using edges with weight <= W" common parallel binsearch problem). Very intuitive when you actually see it
I suggest you to re-invent factorization algorithm which works in $$$O(poly(\log(n)))$$$ time where $$$n$$$ is the number to factorize.
Maybe the HASHTABLE: https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
Such a flex