### Theo830's blog

By Theo830, history, 10 months ago,

Problem: You have some sets and you want to check if set $B$ is subset of set $A$. You can erase or insert any element from any set. Let's say that $Q$ is the number of queries (check,insert or erase) and $Q <= 10^5$.

I think that may exist a solution using hash function. If you find the binary representation of all the sets (a bit is true only if it exists in the set) if there is a way to find the bitwise AND operation of two hash numbers then if $A$ & $B$ $=$ $B$ then $B$ is subset of $A$.

•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 You could try to do sqrt decomposition: If $B$ has a size smaller than $O(\sqrt{Q})$, then check in $O(B)$. Otherwise, there are at most $O(\sqrt{Q})$ different options for $A$ (I assume you check in the beginning that $|A| \geq |B|$), yielding $O(Q)$ pairs in total. Have the answer (more specifically, $|B \setminus A|$) precomputed for all $O(Q)$ pairs. Overall solution would be $O(Q \sqrt{Q})$, if you keep all sets stored as (sparse) hash sets. Better complexities might exist, though.