Computer Science 320SC – (2020)
Exam Creation
Assignment 6 (programming)
Due: Saturday, October 31st
This assignment will test your understanding of applying network flow to solve a con- strained 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 goals, 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
76
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
22
Easy Medium
Graph AdHoc
Funny AdHoc Medium
NotSoFun Graph Hard
Yes No
Submission
For this assignment name your source code examE.ext and examH.ext where ext denotes one of programming language extensions supported by the automarker. There will be two test cases loaded for marks, where three marks are allocated to one (easy) and two marks are allocated for the other (hard). Eight submissions are allowed without penalty; 25% off if you require more, up to a hard limit of 20.