Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Theo830's blog

By Theo830, history, 4 years ago, In English

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?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Lets mantain three sets:

oa — numbers only in A

ob — numbers only in B

oab — numbers in A and B

Check is equal to ob.empty()

Also it is easy to mantain sets after insert/delete

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can this work if there are more than 2 sets?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +15 Vote: I do not like it

      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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.