Problem H
RA Duty Scheduler
Resident Advisors (or RAs) at Virginia Tech are student leaders who are responsible for helping freshmen transition smoothly to college life. Mr. Friedel is trying to design a system to assist him in the process of scheduling RAs to be on duty every month. On each day there are exactly 2 RAs on duty. Unfortunately for Mr. Friedel, each RA is available only on specific days and can only be scheduled then. Before the end of each month, each RA submits a list of days with their availability to Mr. Friedel.
Your goal is to help him write a program that will take a list of RAs and their availabilities and assign two RAs for duty on each day.
While there is no limit for how many days each RA can be on duty, Mr. Friedel wants to reduce unfairness by limiting the imbalance between the number of days each RA is assigned.
Towards that goal, your program needs to minimize the maximum number of days to which any RAs may be assigned.
Input
The input consists of a single test case. The first line contains $2$ numbers $m$ ($2 \le m \le 60$) and $n$ ($28 \le n \le 31$) where $m$ is the number of RAs and $n$ is the total number of days this month. This is followed by $m$ lines where each line consists of the name of the RA followed by an integer $d$ ($1 \le d \le n$) denoting the number of days this RA is available. The remainder of the line consists of $d$ unique integers $i$ ($1 \le i \le n$) denoting the days on which this RA is available. Each RA’s name is a unique string between $1$ and $30$ characters consisting only of English lowercase or uppercase letters. You may assume that there is at least one possible assignment of RAs!
Output
On the first line, output the maximum number of days on which any RA is assigned. Following that, you should output $n$ lines starting with Day k: where $k$ is the number of the day ranging from $1$ to $n$ (inclusive and in order), followed by a space, followed by the names of two RAs scheduled for that day, separated by spaces. The two RAs scheduled for a given day can be listed in any order.
If there are multiple valid assignments, you may output any of them!
| Sample Input 1 | Sample Output 1 |
|---|---|
20 30 Katrina 11 1 3 4 8 10 12 13 15 17 27 29 Pawl 13 3 4 5 6 8 10 11 12 13 15 17 26 27 Sydney 14 1 2 3 4 6 7 8 11 13 14 15 16 28 30 Kylie 15 1 2 4 5 6 8 9 10 12 13 15 16 17 18 27 Meredith 15 1 2 4 7 8 9 11 12 13 25 26 27 28 29 30 Amanda 16 1 2 7 8 9 10 11 14 15 16 17 18 19 28 29 30 Akshay 16 1 2 3 4 6 7 8 12 13 14 15 16 17 28 29 30 Chelsea 17 1 2 3 4 5 7 8 9 11 15 16 17 25 27 28 29 30 Zachary 18 1 3 4 5 6 7 8 9 12 13 14 15 16 17 26 27 29 30 Alex 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 28 29 30 Tariq 19 1 3 4 5 6 8 10 11 12 13 18 19 20 22 24 25 26 27 29 Schlake 21 1 3 4 6 10 11 12 13 15 17 18 19 20 21 22 23 24 25 26 27 29 Joel 23 3 4 5 6 7 8 9 10 11 12 13 14 18 19 20 21 22 23 24 25 26 27 28 Benjamin 23 1 2 3 4 5 6 7 8 9 10 12 13 14 15 18 19 20 21 22 23 24 28 30 Collin 24 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 27 28 29 30 Austin 24 1 2 3 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 28 29 Shahmir 24 1 2 3 4 6 8 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 29 30 Harrison 25 1 2 3 6 7 8 9 10 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Josh 27 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 20 21 22 23 24 25 26 27 28 29 30 Amy 28 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
3 Day 1: Benjamin Katrina Day 2: Amanda Alex Day 3: Alex Katrina Day 4: Akshay Zachary Day 5: Collin Chelsea Day 6: Collin Schlake Day 7: Akshay Sydney Day 8: Pawl Meredith Day 9: Joel Kylie Day 10: Alex Amanda Day 11: Josh Meredith Day 12: Akshay Meredith Day 13: Schlake Sydney Day 14: Shahmir Amy Day 15: Kylie Katrina Day 16: Sydney Amanda Day 17: Amy Harrison Day 18: Collin Kylie Day 19: Harrison Tariq Day 20: Austin Benjamin Day 21: Amy Austin Day 22: Tariq Shahmir Day 23: Austin Joel Day 24: Benjamin Josh Day 25: Joel Tariq Day 26: Schlake Pawl Day 27: Harrison Pawl Day 28: Shahmir Josh Day 29: Chelsea Zachary Day 30: Zachary Chelsea |
