### 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$.

Any ideas about a solution?

• +9

 » 10 months ago, # |   +14 Lets mantain three sets:oa — numbers only in Aob — numbers only in Boab — numbers in A and BCheck is equal to ob.empty()Also it is easy to mantain sets after insert/delete
•  » » 10 months ago, # ^ |   0 How can this work if there are more than 2 sets?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +15 Assuming you have empty sets at first. For sets with >= X values, we maintain them in large boolean arrays and also maintain their pairwise oa ob oab thing. For small sets, we maintain the sorted values in there. So we can solve small-small and small-large in O(X) and large-large in O(1) using O(X*Q) memory and O(X) O(Q/X) time per small/large update. Make X = sqrt(Q) and we get O(sqrt(Q)) per update.
•  » » » 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.