LA 3524

From Algorithmist
Jump to navigation Jump to search

LA 3524 - The Cow Doctor[edit]

Summary[edit]

The doctor has some test materials. Each test material can test a set of diseases. A mixture of two test materials gives a new test material that can test diseases at least one of the mixed materials tested.

Given is a set of test materials. Determine, how many of them are redundant, i.e., can be obtained by mixing some other test materials.

Explanation[edit]

This problem is pretty straightforward.

How to check whether a given test material M is redundant? Consider the set S of all other test materials that test a subset of M's diseases. M is redundant if and only if the mixture of all materials in S tests exactly the same set of diseases as M.

Implementations[edit]

It is convenient to represent the materials as bit vectors.

Input[edit]

10 5
2 1 2
2 2 3
3 1 2 3
4 1 2 3 4
1 4
3 7
1 1
1 2
1 3
2 1 2
2 1 3
2 3 2
3 1 2 3

Output[edit]

2
4