Final Team Match
Time limit2sMemory limit128 MB
Given up to 1000 students each mastering a subset of at most 15 problem types, find the largest group whose combined skill set covers at most K types.
- Level
Medium5 of 10
- Topics
- Bit manipulation, Brute force, Greedy
- Solved
- No attempts yet
Problem
Students may think the mock exam they are taking now is the last event, but one final team match remains after it. In this match, the students will be split into two groups, A and B. This time, the groups will be chosen according to the kinds of algorithm problems each student can solve.
There are N students (1 <= N <= 1,000) and D kinds of algorithm problems (1 <= D <= 15). To keep group A within a target level, choose group A so that the total number of distinct problem kinds solvable by at least one student in group A is at most K (1 <= K <= D). All remaining students go to group B.
During the team match, students may discuss within their group. Therefore, if at least one student in a group can solve a certain kind of problem, every student in that group is considered able to solve that kind.
Under this rule, it is not immediately clear how strong group A can be, so first determine the largest possible number of students in group A. Given the students' information, write a program that computes that maximum size.
Input
The first line contains three integers N, D, and K.
Each of the next N lines describes one student, from student 1 through student N. The first integer on a line is the number of algorithm problem kinds that the student can solve. It is followed by the numbers of those problem kinds. Problem kinds are numbered from 1 to D.
Output
Print the maximum possible number of students in group A.