Kambar_Z's blog

By Kambar_Z, history, 9 months ago, In English

Hello everyone!

While solving a math problem recently, I came up with an interesting trick on sets union. The ordinary solution using inclusion-exclusion principle for 3 sets looks as following:

|x1 ∪ x2 ∪ x3| = |x1| + |x2| + |x3| — (|x1 ∩ x2| + |x1 ∩ x3| + |x2 ∩ x3|) + |x1 ∩ x2 ∩ x3|

Obviously the time complexity to compute union of N sets by this approach is O(2 ^ N).

Now, lets store for each set xi (1 <= i <= N) only those subsets that are not intersected with other subsets on prefix:

u1 = x1

u2 = |x2| — |x2 ∩ u1|

u3 = |x3| — |x3 ∩ u2| — |x3 ∩ u1|

Then answer could be found as following:

|x1 ∪ x2 ∪ x3| = |u1| + |u2| + |u3|

The algorithm is simplified to O(N ^ 2).

But, we can reorder the formula to compute each ui as following:

u3 = |x3| — |x3 ∩ |u1 ∪ u2||

u4 = |x4| — |x4 ∩ |u1 ∪ u2 ∪ u3||

...

Here we only need to maintain the union of previous subsets on prefix, that could be done in O(1) since they do not intersect.

Thus total complexity to find union of N sets is reduced to O(N).

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

»
9 months ago, # |
Rev. 6   Vote: I like it +7 Vote: I do not like it

Hello, I have a more general approach here

You can directly calculate the value of |u1∪u2∪u3∪...∪uk|'s value, then you can get |u1∪u2∪u3∪...∪uk| in O(n)

Don't thank me. CP's knowledge should be shared.


upd: sorry it's O(k) not O(n)