Problem Link - Department Strengths
Problem Statement
The company ZIPCOT Inc. has N employees, who have employee IDs from 1 to N. No two employees have the same employee ID. The company is divided into different departments, and each employee belongs to exactly one department.
The employees in each department are organized hierarchically like a tree. That is, each department has a Department Head, who could have some other employees who work directly under him. Those employees could in turn have more employees under them, and so on. In other words, each employee who is not a Department Head has exactly one manager directly above them.
Each department is classified as either a Type Even department or Type Odd department, based on its size. That is, if the total number of employees in a particular department is even, then that department is of Type Even. Else, it is of Type Odd.
The departments follow a peculiar rule: In every department which is of Type Even, the Department Head of that department will have the smallest employee ID among the employees in that department. And in every Type Odd department, the Department Head will have the largest employee ID among all the employees in that department.
For example, a valid department could be: Employee 3 is the Head, who has employees 5 and 7 under him. Employee 5, in turn, has the employees 4, 8 and 9 under him. This follows the rule, because there are 6 employees in this department, which is even, and the Head (3) is the smallest employee ID among {3, 4, 5, 7, 8, 9}.
Each employee also has a Level associated with them, which measures how far down they are from the Department Head of their department. In particular, all Department Heads are in Level 1. The employees directly beneath them are in Level 2, and so on. Formally, the Level of an employee who is not a Department Head is 1 + the Level of their manager.
The company is organizing a programming competition, and the departments are divided into two teams based on their Type. All the employees from Type Even departments form one team. And all the employees from Type Odd departments form the other team. The Strength of a team is defined to be the sum of Levels of all the employees in it. You need to find the Strength of both the teams.
Approach
The problem involves identifying connected components in a graph, where each component represents a department. The BFS (Breadth-First Search) algorithm is used to traverse each component and determine the Level of each employee. For each department, we calculate its size and classify it as Type Even or Type Odd based on whether its size is even or odd. Depending on the type, the smallest or largest employee ID is chosen as the Department Head. After identifying the Department Head, we run BFS again to calculate the sum of Levels for all employees in that department. Finally, we accumulate these sums separately for Type Even and Type Odd departments.
Time Complexity
The time complexity is O(N + M), where N is the number of employees and M is the number of connections (manager-employee relationships).
Space Complexity
The space complexity is O(N + M) to store the graph and auxiliary arrays for BFS traversal.