Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

alpenglow's blog

By alpenglow, history, 6 weeks ago, In English

Please help me solve the following problem:

Given N (N <= 100 000) small sets (size at most 7). find number of non-intersecting pairs among these sets.

Thanks for your attention.

P.S. I'm reposting this because the previous blog got heavily downvoted for nothing and does not get bumped up in the recent actions. Nobody has yet found the correct solution.

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Have you considered that duplicating your original post may not be the best way to attract serious answers? The main reason I didn't even attempt to help on your original post was that I wasn't able to quickly identify the source of the problem; this issue remains unresolved by this re-post.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was solving this CSES problem with this observation that with the constraints given the numbers can have at most 7 distinct prime factors.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      OK. The first approach that came to my mind was inclusion-exclusion over common elements in the set: Add one for every pair of indices $$$(i, j)$$$, subtract one for every tuple $$$(\{x\}, i, j)$$$ with $$$x \in A_i \cap A_j$$$, add one for every tuple $$$(\{x, y\}, i, j)$$$ with $$$x \neq y$$$ and $$$\{x, y\} \subseteq A_i \cap A_j$$$, and so on. But it is clear that only the sets $$$S$$$ which are subsets of at least one $$$A_i$$$ can contribute to the sum, and there are at most $$$2^7 \cdot 10^5$$$ such sets, and the contribution of each to the sum can be maintained using a hash-map: Process the sets in the input one at a time, and for each subset $$$S \subseteq A_i$$$, add or subtract as appropriate the number of input sets $$$A_j$$$ already encountered with $$$S \subseteq A_j$$$.

      However, with sets of common prime factors of numbers less than $$$10^6$$$, there is a natural and obvious perfect hash function: the product, and so an array can be used instead.

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

This exact problem has shown up in USACO before (albeit with slightly smaller constraints). link