Set-trie: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «==Задача== Дано $S$ множеств, суммарного размера $sum$, дается множество $x$, требуется провер...») |
|||
(не показана 1 промежуточная версия 1 участника) | |||
Строка 5: | Строка 5: | ||
==Решение== | ==Решение== | ||
− | Отсортируем все множества в лексикографическрм порядке, затем сложим их в бор, теперь отсортируем также множество $x$, заметим, что подмножество $x$ есть в | + | Отсортируем все множества в лексикографическрм порядке, затем сложим их в бор, теперь отсортируем также множество $x$, заметим, что подмножество $x$ есть в $S$ тогда и только тогда, когда есть хоть один путь, заканчивающийся в терминальной вершине бора, который является подмножеством $x$, тогда давайте идти по множеству $x$, пусть мы сейчас смотрим на $x_{i}$ и стоим в вершине $v$, пусть в боре из $v$ есть переход по $x_{i}$, запустимся рекурсивно в него, уже рассматривая $(i+1)$-ый элемент, если мы не нашли подмножество, то запустимся из вершины v, рассматривая $(i+1)$-ый элемент. |
==Асимптотика== | ==Асимптотика== | ||
Строка 12: | Строка 12: | ||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
+ | |||
+ | [[Категория:Конспект]] |
Текущая версия на 21:27, 8 мая 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