INOI1601 - Editorial

Problem Link - Wealth Disparity

Problem Statement:

Indian National Olympiad in Informatics 2016

Boing Inc, has N employees, numbered 1 ... N. Every employee other than Mr. Hojo (the head of the company) has a manager (P[i] denotes the manager of employee i). Thus an employee may manage any number of other employees but he reports only to one manager, so that the organization forms a tree with Mr. Hojo at the root. We say that employee B is a subordinate of employee A if B appears in the subtree rooted at A.

Mr. Hojo, has hired Nikhil to analyze data about the employees to suggest how to identify faults in Boing Inc. Nikhil, who is just a clueless consultant, has decided to examine wealth disparity in the company. He has with him the net wealth of every employee (denoted A[i] for employee i). Note that this can be negative if the employee is in debt. He has already decided that he will present evidence that wealth falls rapidly as one goes down the organizational tree. He plans to identify a pair of employees i and j, j a subordinate of i, such A[i] - A[j] is maximum. Your task is to help him do this.

Suppose, Boing Inc has 4 employees and the parent (P[i]) and wealth information (A[i]) for each employee are as follows:

i		1	2	3	4
A[i]		5	10	6	12
P[i]		2	-1	4	2
P[2] = -1 indicates that employee 2 has no manager, so employee 2 is Mr. Hojo.

In this case, the possible choices to consider are (2,1) with a difference in wealth of 5, (2,3) with 4, (2,4) with -2 and (4,3) with 6. So the answer is 6.

Approach:

To solve this problem, we can use a Depth-First Search (DFS) on the organization tree, rooted at Mr. Hojo. First, we build an adjacency list representation of the tree, where each employee points to their direct subordinates. Then, starting from Mr. Hojo, we traverse the tree recursively. For each node during traversal, we keep track of the maximum wealth encountered from the root down to the current node, as well as the maximum disparity (maxDisp) found so far. For each employee i we visit, we compute the difference maxWealth - A[i] to find how much wealth drops as we move down the tree. If this difference is greater than the current maxDisp, we update maxDisp. After visiting all subordinates of each employee, we return the maximum disparity found.

Time Complexity:

O(N), where N is the number of employees, because we visit each employee exactly once in the DFS traversal.

Space Complexity:

O(N), for storing the adjacency list representation of the tree and the recursion stack in the worst case.