Connection Status:
Competition Arena > Graduation

Graduation

SRM 200 · 2004-06-21 · by antimatter

SRM 200 · 2004-06-21 · by antimatter · Graph Theory
Class Name: Graduation
Return Type: String
Method Name: moreClasses
Arg Types: (string, vector<string>)
Problem Statement

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".

Notes

  • Classes may not be taken more than once.

Constraints

  • 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
Examples
0)
"A"
{"2ABC","2CDE"}
Returns: "BCD"

The student must take two classes from {A,B,C}, and two from {C,D,E}. He has already taken A.

1)
"+/NAMT"
{"3NAMT","2+/","1M"}
Returns: ""

The student has already fulfilled all the requirements - you should congratulate him for his achievement!

2)
"A"
{"100%*Klju"}
Returns: "0"

No matter how hard you try, you can't take 100 classes out of 6. TCU had better fix their policies quick.

3)
""
{"5ABCDE","1BCDE,"}
Returns: ",ABCDE"
4)
"hi"
{"100",
 "16abcdefghijklmnopqrstuvwxyz",
 "21ABCDEFGHIJKLMNOPQRSTUVWXYZ",
 "43!@#$%^&*()~-=\\{}[];:\"'<>,.?/"}
Returns: "0"

Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Graduation with a public method string moreClasses(string classesTaken, vector<string> requirements) · 50 test cases · 2 s / 256 MB per case

Submitting as anonymous