Set-trie: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «==Задача== Дано $S$ множеств, суммарного размера $sum$, дается множество $x$, требуется провер...») |
Глеб (обсуждение | вклад) |
||
Строка 5: | Строка 5: | ||
==Решение== | ==Решение== | ||
− | Отсортируем все множества в лексикографическрм порядке, затем сложим их в бор, теперь отсортируем также множество $x$, заметим, что подмножество $x$ есть в | + | Отсортируем все множества в лексикографическрм порядке, затем сложим их в бор, теперь отсортируем также множество $x$, заметим, что подмножество $x$ есть в $S$ тогда и только тогда, когда есть хоть один путь, заканчивающийся в терминальной вершине бора, который является подмножеством $x$, тогда давайте идти по множеству $x$, пусть мы сейчас смотрим на $x_{i}$ и стоим в вершине $v$, пусть в боре из $v$ есть переход по $x_{i}$, запустимся рекурсивно в него, уже рассматривая $(i+1)$-ый элемент, если мы не нашли подмножество, то запустимся из вершины v, рассматривая $(i+1)$-ый элемент. |
==Асимптотика== | ==Асимптотика== |
Версия 11:20, 19 марта 2020
Задача
Дано $S$ множеств, суммарного размера $sum$, дается множество $x$, требуется проверить есть ли среди $S$ множеств хотя бы одно его подмножество.
Решение
Отсортируем все множества в лексикографическрм порядке, затем сложим их в бор, теперь отсортируем также множество $x$, заметим, что подмножество $x$ есть в $S$ тогда и только тогда, когда есть хоть один путь, заканчивающийся в терминальной вершине бора, который является подмножеством $x$, тогда давайте идти по множеству $x$, пусть мы сейчас смотрим на $x_{i}$ и стоим в вершине $v$, пусть в боре из $v$ есть переход по $x_{i}$, запустимся рекурсивно в него, уже рассматривая $(i+1)$-ый элемент, если мы не нашли подмножество, то запустимся из вершины v, рассматривая $(i+1)$-ый элемент.
Асимптотика
Асимптотика данного решения - $O(sum)$, если множества уже отсортированы, несложно придумать решение двумя указателями за такую же асимптотику, интереснее константа этого решения на случайных данных.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin