Automatic Control Machine
Time limit2sMemory limit1024 MB
Given up to 15 binary strings of length n, pick the fewest strings whose bitwise OR covers every position, or report -1.
- Level
Medium6 of 10
- Topics
- Bit manipulation, Brute force, Greedy, Implementation
- Solved
- No attempts yet
Problem
The company has produced an Automatic Control Machine (ACM for short) that is very popular. Its features are complete and powerful, so after years of sales the company is preparing to redesign it. The new version of the ACM still has to go through a number of tests to determine the reliability of the product before it goes on the market. Because there are so many features, each test dataset can only detect several of them. Of course, the product can be released only after all features have been tested. Since each test has time and material costs, they want to run as few tests as possible. Assume that running each test dataset costs the same, and find the minimum number of test datasets that can cover the test of all features. For example, suppose there are 5 features that need to be tested, and there are 6 test datasets, each covering the following features:
- Test dataset a: 1
- Test dataset b: 2, 5
- Test dataset c: 2, 3, 4
- Test dataset d: 1, 3, 5
- Test dataset e: 1, 3, 4
- Test dataset f: 3, 5
Although {a, b, c} may do the job, {c, d} will do the job better in the way of saving time and money.
Input
The first line of the input file contains one positive integer T representing the number of machines. For each machine, the first line consists of two integers n and m representing the features of the machine that have to be tested and the number of test datasets. It follows by m lines, each line has a binary string of length n, showing whether the features can be detected by the test dataset or not (1 means yes, 0 means no).
Output
Output T lines. Each of them should be the minimum number of test datasets needed to test all features for that machine. If it is not possible to test all functions for the machine, output -1.
Constraints
- The number of machines 0 < T ≤ 10
- The number of functions to be tested 0 < n ≤ 500
- The number of test data 0 < m ≤ 15