s
b
a
d
c
f
e
h
g
t
3.
You are scheduling initial phone interviews for n job candidates that
have applied to di↵erent jobs at the same company (each candidate has
applied to just one job). The company has k n recruiters, and each
recruiter is qualified to interview candidates only for some of the jobs.
Each candidate needs to be assigned to a recruiter to be interviewed.
Candidates are labeled 0, 1, . . . , n 1, and recruiters are labeled n, n
1, . . . , n k 1. For each candidate i, R i n, n 1, . . . , n k 1
holds the recruiters that can interview candidate i. You want to make
sure that recruiters are not overloaded: u j is the maximum number
of interviews that recruiter j can do.
Someone has already tried to find an assignment of candidates to in-
terviewers, but they are having trouble. They have an array A that
assigns each candidate i to recruiter A i (without overloading any re-
cruiter). Unfortunately, A n 1 is blank, and they are having trouble
3
filling this last entry.
You must code an e�cient algorithm that has the following behavior:
If there exists a valid assignment that assigns all job candidates
to recruiters, output it. Note that there may be more than
one such valid assignment. We will accept any, as long as
it is assigns all job candidates to recruiters in a valid way (i.e.,
no recruiter is overbooked, and each candidate i is assigned a
recruiter in S i ).
If no such assignment exists, you plan to ask one of the recruiters j
to increase their capacity u j by 1. Output the list of recruiters
j such that if their capacity is increased by 1 (while the other
capacities remain the same), then a solution will exist.
Your algorithm must run in O m time, where m
n 1
i 0 S i
is the number of pairs of candidate and recruiter who could interview
the candidate.
Input / output formatting and requirements.
Your algorithm is to read data from stdin in the following format:
The first line has two numbers, n 10
5
and k 10
5
, the number
of candidates and recruiters.
In the i 1
th
line of the next n lines (for i 0, . . . , n 1) gives
the indices of the recruiters who can interview candidate i. In
other words, the i 1
th
line gives the elements of the set Si.
The next line has k numbers representing the capacities of the
recruiters. In other words, the `
th
number on this line is u n
1 ` , the capacity of the `-th recruiter (who, as explained above,
has label n 1 `).
The last line has n 1 numbers representing the preliminary
assignment; in other words, the i 1
th
number is A i (where
A i is a recruiter label, so it is an integer between n and n k 1).
Your algorithm should output data to stdout in two lines:
If there exists a full assignment, the first line will be “Yes”, and
the second line should have n integers where the i-th value is the
recruiter that the i-th candidate is assigned to.
If there does not exist an assignment, the first line will have the
string “No”, and the second line should have k values where the
4
`-th entry is 1 if increasing the capacity u n 1 ` of the `-th
recruiter (leaving the other capacities the same) would make a
full assignment possible, and 0 otherwise.
Example.
When the input is:
3 2
3 4
3
3
2 1
3 3
there are 3 candidates labeled 0, 1, 2, and 2 recruiters labeled 3, 4.
Candidate 0 can be interviewed by recruiters 3 and 4, and candidates
1 and 2 can be interviewed by recruiter 3 only. Recruiter 3 has the
capacity to interview 2 candidates, and recruiter 4 can interview 1
candidate. The preliminary assignment has assigned candidates 0 and
1 to recruiter 3.
A fully satisfying assignment does exist, because we can assign candi-
date 0 to recruiter 4, and candidates 1 and 2 to recruiter 3. So you
should output:
Yes
4 3 3
When the input is:
3 2
3 4
3
3
1 2
4 3
the input is almost the same as before, except the capacities of the
two recruiters are flipped: recruiter 3 has capacity 1, and recruiter 4
has capacity 2. The preliminary assignment has assigned candidate 0
5
to recruiter 4 and candidate 1 to recruiter 3. In this case, no fully sat-
isfying assignment exists, and the only way to create one is to increase
the capacity of recruiter 3. So the output should be:
No
1 0
Hint: apply what you learned in lecture – just trying to develop your
own algorithm without using techniques from lecture is unlikely to work
for all test cases. Also, you might find you can reuse some parts of the
code you wrote for Homework 2!
6