TopCoder problem "Graduation" used in SRM 200 (Division I Level Three)

Problem Statement


You are a student advisor at TopCoder University (TCU). The graduation requirements at TCU are somewhat complicated. Each requirement states that a student must take some number of classes from some set, and all requirements must be satisfied for a student to graduate. Each class is represented as a single distinct character. For example, one requirement might be "Take any 2 classes of B, C, D, or F." Further complicating the matter is the fact that no class can be used to satisfy more than one requirement. And so students come to you all the time, dazed and confused, because they don't know how close they are to satisfying the requirements so that they can graduate!

Each class is represented as a distinct single character whose ASCII value is between 33 and 126, inclusive, but is also not a numeric character ('0'-'9'). You will be given a String classesTaken, which represents the classes that a given student has taken. You will also be given a String[] requirements, which lists the requirements needed to graduate. Each String in requirements will start with a positive integer, followed by some number of classes. For example, the requirement "Take any 2 classes from B, C, D, or F" would be represented in requirements as "2BCDF".

Your method should return a String representing the classes that the student needs to take in order to graduate, in ASCII order. Classes may not be taken more than once. If there is more than one set that will allow the student to graduate, return the smallest set. If there are multiple smallest sets, return the lexicographically smallest of these. Finally, if there is no set that will enable this student to graduate, return "0".



Parameters:String, String[]
Method signature:String moreClasses(String classesTaken, String[] requirements)
(be sure your method is public)


-Classes may not be taken more than once.


-classesTaken will be between 0 and 50 characters in length, inclusive.
-each character in classesTaken will be a valid class (ASCII value between 33 to 126 inclusive and not a digit).
-there will be no duplicate classes in classesTaken.
-requirements will contain between 1 and 50 elements, inclusive.
-each element of requirements will contain a positive integer with no leading zeros between 1 and 100, inclusive, followed by some number of valid classes.
-each element of requirements will be between 1 and 50 characters in length, inclusive.
-there will be no duplicate classes in any given element of requirements


Returns: "BCD"
The student must take two classes from {A,B,C}, and two from {C,D,E}. He has already taken A.
Returns: ""
The student has already fulfilled all the requirements - you should congratulate him for his achievement!
Returns: "0"
No matter how hard you try, you can't take 100 classes out of 6. TCU had better fix their policies quick.
Returns: ",ABCDE"
{"2AP", "3CDEF", "1CDEFH"}
Returns: "AEP"

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Graph Theory