Inclusion Exclusion Problem

Revision en1, by Abdelaleem_Ahmed, 2022-09-08 03:38:27

========

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Abdelaleem_Ahmed 2022-09-08 03:38:27 780 Initial revision (published)