Abdelaleem_Ahmed's blog

Inclusion Exclusion Problem
By Abdelaleem_Ahmed, history, 2 years ago, In English

========

Problem:

Given a list of N items. Each item can be assigned to multiple categories. How many ways can I take a pair of items that don't share a common category?

constraints:

  1. Number of items <= 100,000.
  2. Number of categories <= 30.
  • Each item can be assigned to a maximum of 30 different categories.

Example:

We have 5 items

1st item is assigned to categories: 1, 3, and 5.

2nd item is assigned to categories: 2, and 6.

3rd item is assigned to categories: 2, 3, and 5.

4th item is assigned to category: 4.

5th item is assigned to categories: 1, and 2.

Answer is 5

(1,2),(1,4),(2,4),(3,4),(4,5).

Can anyone help me with how can I solve this problem?

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

Comments Comments (10)
| Write comment?
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can you provide link to original statement?

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

[DELETED]

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    " the number of pairs you can't choose is much smaller than the total possible number of pairs "

    What if all items belong to only 1 category, there will be O(N^2) pairs

    " With some numbers, in one category you can have at most 30 different elements those are (30 * 29) / 2 possible pairs which sums up to 435 possible different pairs "

    What is some number? What are you considering as elements in a category? If you are considering it to be having a common group then this can be a lot bigger considering the above case.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You are totally right, I messed up the interpretation, I don't know how to solve the problem.

      → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Please explain the statement clearly. What is given in the input? The number of items as well as the category of each item? Are pairs $$$(a,b)$$$ and $$$(b,a)$$$ different?

If so then iterate over all pairs of categories $$$(c1,c2)$$$ and then add $$$freq[c1] * freq[c2]$$$ to your answer.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You are misunderstanding the problem. Given a list of N items. Each item is assigned a list of categories(categories are represented by integer from 1 to M) . So you are given A: vector of vector which contains N items and A[i] is a vector which contains the categories which item i belongs to.

    Find number of pairs of (i,j) such that i < j and the items don't have a common category (i.e no a,b exists such that A[i][a] = A[j][b])

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

      Sorry for the delay in replying, and thanks for the help in advance.

      I think adityagamer explained the problem nicely better than I did.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure about the constraint on number of categories? I saw a kinda similar problem but with constraint on number of categories <= 10.

For this constraint it can be solved in the following way:

Convert every element to its corresponding bit representation. For example if it has categories {1,3,5} then its bit representation is 10101. Now for every element i, we need to query number of elements such that they do not share any bit with ith element. Optimization 1: Take mask = ~element[i] and then you need to find number of elements x in array such that mask|x = mask. Optimization 2: There can be atmost 2^10 different queries, so it would be better to cache the result of queries(Or you can also just simply do offline queries). Finally just divide the answer by 2. Overall complexity = O(N * 2^M)

→ Reply