This assignment will test your understanding of applying network flow to solve a constrained selection problem.
computer science
Description
Computer Science – 2020
Assignment 2.3
Exam Creation
This assignment will test your understanding of applying network
flow to solve a constrained selection problem. We want to decide if we have enough questions (in a database) of a particular type and difficulty
level to create a good exam to assess
an algorithms course.
Your teacher’s main goal,
as designer, is to provide a range of difficulty
(such as Easy, Medium, Hard) and a diversity of topics (such as Brute Force, Divide and Conquer, Dynamic Programming). For example, the exam should
have a couple very easy
questions and should
have at least one really hard question. At disposal is a database
of questions of various topics
and difficulty levels.
We have a requirement to (hopefully) pick a subset of these questions to use as the composition of a final
exam. Your task for this assignment is to write
a program that checks if we can fulfill
the requirements for a good exam to assess the class.
If not, your teacher will
be forced to develop a few new questions for the database.
Input
The input consists of a series
of up to 1000 test
cases. This integer is given
on the first line of the input.
Each test case begins with
a line consisting of two integers
1 ≤ n ≤ 2000 and
1 ≤ m ≤ 500, denoting the number of questions
in the exam database and the number of questions needed for the exam, respectively. The second
line contains m strings (duplicates allowed), denoting the difficulty of the questions wanted for the exam.
The third line
contains m strings (duplicates allowed), denoting the topics of coverage
required for the exam. The next n lines contain a description of the questions in the database. Each line contains three strings: the name of the question, the assessment topic
and the difficulty of the question. The names of the n questions will
be distinct. All strings in the input
will only contain letters and digits
(no spaces), with each length at most twenty characters.
Output
If there are m distinct questions that satisfy the requirements of the exam, then output
Yes. Otherwise output
No.
Sample input and output
|
Input |
Output |
|
2 |
Yes |
|
7 6 |
No |
|
Easy Easy Medium
Medium Hard Hard |
|
|
Graphs Brute
AdHoc Brute Geometry Math |
|
|
SexyLife Brute
Medium |
|
|
BottomFeeder Graphs
Hard |
|
|
BadCase AdHoc Easy |
|
|
Dominos Graphs Medium |
|
|
Elephant Brute
Hard |
|
|
Flash Geometry Medium |
|
|
Geography Math Easy |
|
|
2 2 |
|
|
Easy Medium |
|
|
Graph AdHoc |
|
|
Funny AdHoc
Medium |
|
|
NotSoFun Graph Hard |
Submission
For this
assignment name
your source code examE.ext and examH.ext where ext
denotes one of the automarker supported languages (Python). Use just one source
file per problem. Here the suffix E
denotes ‘E’asy (test
data) and H
denotes ‘H’arder (test
data). Three
marks is allocated to examE.ext and two marks
are allocated for examH.ext.
