TopCoder problem "SpreadingNews" used in SRM 316 (Division II Level Three)



Problem Statement

    

You are the manager of a company, and you want all of your employees to be notified of an important news item as quickly as possible. Your company is organized in a tree-like structure: each employee has exactly one direct supervisor, no employee is his own direct or indirect supervisor, and every employee is your direct or indirect subordinate. You will make a phone call to each of your direct subordinates, one at a time. After hearing the news, each subordinate must notify each of his direct subordinates, one at a time. The process continues this way until everyone has heard the news. Each person may only call direct subordinates, and each phone call takes exactly one minute. Note that there may be multiple phone calls taking place simultaneously. Return the minimum amount of time, in minutes, required for this process to be completed.

Employees will be numbered starting from 1, while you will be numbered 0. Furthermore, every supervisor is numbered lower than his or her direct subordinates. You are given a int[] supervisors, the ith element of which is the direct supervisor of employee i. The first element of supervisors will be -1, since the manager has no supervisors.

 

Definition

    
Class:SpreadingNews
Method:minTime
Parameters:int[]
Returns:int
Method signature:int minTime(int[] supervisors)
(be sure your method is public)
    
 

Constraints

-supervisors will contain between 1 and 50 elements, inclusive.
-Element i of supervisors will be between 0 and i-1, inclusive, except for the first element which will be -1.
 

Examples

0)
    
{-1, 0, 0}
Returns: 2
Call subordinate 1 at time 0 and then subordinate 2 at time 1. By time 2, both subordinates will have heard the news.
1)
    
{-1, 0, 0, 2, 2}
Returns: 3
This time call employee 2 first, and then employee 1 at time 1. After hearing the news, employee 2 will call employee 3 at time 1 and employee 4 at time 2. It takes 3 minutes for everybody to hear the news.
2)
    
{-1, 0, 1, 2, 3}
Returns: 4
Everyone in the company has only one subordinate, resulting in a chain of phone calls.
3)
    
{-1, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 12, 13, 14, 16, 16, 16}
Returns: 7

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6538

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9996&pm=6538

Writer:

_efer_

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Graph Theory, Greedy, Recursion