Is it possible to solve this problem fast?

Правка en1, от Theo830, 2020-12-13 14:11:11

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?

Теги hashing, subset

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Theo830 2020-12-13 14:11:11 573 Initial revision (published)