Set-trie

Задача

Дано $S$ множеств, суммарного размера $sum$, дается множество $x$, требуется проверить есть ли среди $S$ множеств хотя бы одно его подмножество.

Решение

Отсортируем все множества в лексикографическрм порядке, затем сложим их в бор, теперь отсортируем также множество $x$, заметим, что подмножество $x$ есть в $S$ тогда и только тогда, когда есть хоть один путь, заканчивающийся в терминальной вершине бора, который является подмножеством $x$, тогда давайте идти по множеству $x$, пусть мы сейчас смотрим на $x_{i}$ и стоим в вершине $v$, пусть в боре из $v$ есть переход по $x_{i}$, запустимся рекурсивно в него, уже рассматривая $(i+1)$-ый элемент, если мы не нашли подмножество, то запустимся из вершины v, рассматривая $(i+1)$-ый элемент.

Асимптотика

Асимптотика данного решения - $O(sum)$, если множества уже отсортированы, несложно придумать решение двумя указателями за такую же асимптотику, интереснее константа этого решения на случайных данных.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin