Set-trie

Материал из Algocode wiki
Версия от 21:27, 8 мая 2020; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

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

Решение

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

Асимптотика

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



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

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