Hello, codeforces community!

I am happy to invite you to participate in Shorouk Academy 2024 Collegiate Programming Contest that will held at Shorouk Academy. The online training will be on codeforces gyms and will start on Saturday, April 27, 2024 at 11:00 EEST.

The unofficial contest will take place in Codeforces Gym, following standard ICPC rules where individual and team participation are allowed. The contest is unrated and will last for 5 hours, featuring 13 problems.

The problems are written and prepared by only me — Abdelaleem_Ahmed.

Thanks to khepri, SalahSalem, HitmanX97, AbdalrhmanEssam, 3zim, Eslam_Ahmed, Abwbkr, OMAR_TAHA, ipy_, Ahmed_Dyab, Dr.rabi3, Glitch00, A7md_Roshdy, AhmedEhab, --ALPHA-- for solo testing.

Thanks to Shorouk Academy for hosting the onsite contest.

Thanks to Polygon for providing the amazing platform for creating and preparing the problems, and to codeforces for the hosting of the online training.

I hope you enjoy solving the problems. Any feedback will be appreciated.

========

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?