BobTrouble

SRM 292 · 2006-03-06 · by dgoodman

SRM 292 · 2006-03-06 · by dgoodman · Graph Theory

Show categories

Class Name: BobTrouble

Return Type: int

Method Name: minSupers

Arg Types: (vector<string>, vector<string>)

Problem Statement

My company has given me a list containing the name of each employee along with the name of his supervisor (who is also an employee) if he has one. The company wants to know whether the list is consistent and, if so, how many of the employees are supervisors (supervise at least one employee). "Consistent" means that there is no supervision cycle in which A supervises himself or A supervises B who supervises C ... who supervises A. It is permissible to have multiple employees who have no supervisor.

But ... we have Bob trouble. All the employees have distinct names, except that there may be multiple distinct employees whose names are "BOB". So there may be multiple ways to put together the supervision hierarchy. We want to construct the hierarchy so as to minimize the number of supervisors.

Create a class BobTrouble that contains a method minSupers that is given a String[] name and a String[] bossName giving the names of all the employees and their bosses. It returns the minimum number of supervisors that can appear in the supervision hierarchy. If no supervision hierarchy is consistent, it returns -1.

Each element of name refers to a distinct employee, and the supervisor of the i-th element is given by the i-th element of bossName ("*" indicates that the employee has no supervisor). Every employee is listed in name.

Constraints

name contains between 1 and 50 elements, inclusive.
Each element of name contains between 1 and 10 uppercase letters ('A'-'Z'), inclusive.
The elements of name are distinct, except that "BOB" may appear more than once.
bossName contains the same number of elements as name.
Each element of bossName is "*" or matches at least one element of name.

Examples

{"BOB","BOB","BOB"}
{"BOB","*","BOB"}
Returns: 1

There are 3 possible supervisory hierarchies: 1) the middle BOB supervises the first BOB who supervises the last BOB, 2) the middle BOB supervises the last BOB who supervises the first BOB, and 3) the middle BOB supervises the first BOB and also supervises the last BOB. This last choice gives the fewest supervisors.

{"JOHN","AL","DON","BOB"}
{"*","*","*","*"}
Returns: 0

All the employees are unsupervised, so there are no supervisors.

{"BOB","BOB","BOB"}
{"*","*","BOB"}
Returns: 1

There are 2 possible hierarchies (the third BOB can be supervised by either of the other BOBs). Either way, exactly one of the BOBs is a supervisor.

{"BOB","BOB","J","K","L","M"}
{"K","J","BOB","J","M","*"}
Returns: -1

{"BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB"}
{"BOB","BOB","*","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB","BOB"}
Returns: 1

{"BOB", "BOB", "JACK"}
{"BOB", "BOB", "*"}
Returns: -1

The first BOB must be supervised by the second BOB (it is illegal to supervise yourself) and the second BOB must be supervised by the first BOB. But this is a supervision cycle, so there is no legal hierarchy satisfying this data.

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

Coding Area

Language: C++17 · define a public class BobTrouble with a public method int minSupers(vector<string> name, vector<string> bossName) · 164 test cases · 2 s / 256 MB per case