Death_Node's blog

By Death_Node, history, 3 weeks 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?

Read more »

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