1092. Covering Everything, Greedily
The numbers 1 to m must all be covered. k sets are given, each a
list of numbers from that range. Choose as few sets as possible so that every number from 1 to
m appears in at least one chosen set.
The obvious rule is GREEDY: repeatedly take the set covering the most numbers that are still uncovered, breaking ties by the smallest set index.
Print two integers: how many sets that rule uses, and the true minimum. If the sets together do
not cover everything, print -1 -1.
m = 6, sets {1,2,3,4} {1,2,5} {3,4,6} -> 3 2
m = 4, sets {1,2} {3,4} -> 2 2
m = 3, sets {1} {2} -> -1 -1
## Trace the first row
The greedy takes {1,2,3,4}, which covers four new numbers against three for each of the
others. That leaves 5 and 6 uncovered, and no single set holds both, so it takes two
more: three sets in all.
The true answer is two: {1,2,5} and {3,4,6} together cover everything. The greedy's
first move, the locally biggest one, is exactly what forecloses it.
## Why this greedy is famous anyway
Unlike the failures in #1039, #1089, #1090 and #1091, this one is not merely wrong, it is the
BEST KNOWN practical rule: no algorithm running in reasonable time is known to do
better in general, because exact set cover is NP-hard. The greedy is provably within a factor
of about ln m of the optimum, and that factor is known to be essentially the best any
efficient algorithm can guarantee.
So this problem is a different lesson from the others. There the greedy should simply not be used. Here it should, with the knowledge that it is an approximation rather than an answer.
## Computing the greedy
Represent each set as a bitmask over the m numbers.
covered = 0, used = 0
while covered != all:
pick the set adding the most new bits, smallest index on ties
if it adds nothing, stop impossible, though the coverage test catches it first
covered |= that set; used += 1
## Computing the true minimum
A table over SUBSETS, which is problem #590's recurrence:
dp[0] = 0
for every reachable state s:
for every set S:
dp[s | S] = min(dp[s | S], dp[s] + 1)
answer = dp[all]
That is 2^m states times k sets, which at m = 16 and k = 16 is about a million
steps.
## The bit index, and the off-by-one
Number e is bit e - 1, because the numbers start at 1 and bits start at 0. Using bit
e instead makes all one bit too wide and the answer never terminates.
all is (1 << m) - 1. At m = 16 that is 65535, comfortably inside a 32 bit integer,
but a solution written for a larger m must be careful: 1 << 31 is negative in a signed
32 bit type.
## The impossible case
Check the union of every set against all BEFORE running either method. The greedy would
otherwise loop forever, or stop having covered a strict subset and report a number that means
nothing.
## Overflow
m reaches 16, so masks fit in 16 bits and the table has 65536 entries. Counts are at most
k = 16. The 32 bit limit of 2147483647 is not in play.
## Cost
Time O(2^m * k) for the table, O(k^2 * m) for the greedy. Space O(2^m).
Constraints - `1 ≤ m ≤ 16` - `1 ≤ k ≤ 16` - each set has between 0 and `m` distinct members, each from 1 to `m`
Input
The first line contains two integers m and k.
Each of the next k lines describes one set: its size, then that many distinct integers from 1 to m.
Output
Print two integers on one line separated by a single space: the number of sets the greedy rule uses, then the true minimum. Print -1 -1 if the sets together do not cover every number from 1 to m. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.