# LA 3524

From Algorithmist

## 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