INOI 2016: Wealth Disparity

Computer Science Level 5

In a company, there are $N$ employees labelled $1,2,3 \ldots , N$ . The organizational structure of the company forms a tree-like hierarchy.

$P_i$ denotes the manager of employee $i$ .
For each employee $i$ , $A_i$ denotes the wealth of employee $i$ .

We say that employee $j$ is the subordinate of employee, $i$ if employee $j$ appears in a subtree rooted at $i$ .

Your task is to find a pair of employees $(i,j)$ , $j$ a subordinate of $i$ , such that $A_i - A_j$ is maximized. Enter your answer as the value of $A_i - A_j$ .

Here is the data.

Input Format

The first line contains $N$ .
The second line contains $A_1, A_2, \ldots A_N$ .
The third line contains $P_1, P_2, \ldots P_N$ . If $i$ is the boss of the company, he has no manager, i.e, $P_i = -1$

Example

Input:

1
2
3

4
5 10 6 12
2 -1 4 2

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

The answer is 199124525.

1 solution

Agnishom Chattopadhyay
Jul 18, 2016

The simplest way to solve this problem is to consider all pairs $(i,j)$ where $j$ is a subordinate of $i$ . To do this, we could pick each node and climb upto the root whilst keeping track of the maximum difference.

Clearly, this is a $O(N \cdot h)$ solution where $h$ stands for height. For a random tree, this tends to be $O(N \log N)$ , however in the worst case, i.e, when the tree is a long chain, the complexity becomes $O (N^2)$ .

Turns out we can do better.

Notice that the maximum difference between a fixed node $i$ and some node $j$ in its subtree can be found by simply finding the minimum value in the subtree, which can be done using a DFS.

So, the key is to use a DFS to get the minimum at each subtree and for each node, check if the maximum possible difference from this node to the minimum in the corresponding subtree is greater than what we've encountered so far.

This is an $O(N)$ solution since we run the processing at each node only once.

#include <iostream>
#include <vector>

typedef std::vector<int> vi;
typedef std::vector<vi> vvi;

vi wealth;
vvi tree;

int maxDiff = -1000000;

int getMin(int node){
  int minHere = wealth[node];
  for (int u: tree[node]){
    int minBranch = getMin(u);
    minHere = std::min(minBranch, minHere);
    maxDiff = std::max(maxDiff, wealth[node]-minBranch);
  }
  return minHere;
}

int main(){
  int N;
  std::cin >> N;
  wealth.resize(N+1);
  for (int iii=1; iii <= N; iii++)
    std::cin >> wealth[iii];

  //convert to Adjacency List representation
  int root;
  tree.resize(N+1);
  for (int iii=1; iii <= N; iii++){
    int parent;
    std::cin >> parent;
    if (parent == -1)
      root = iii;
    else
      tree[parent].push_back(iii);
  }

  getMin(root);

  std::cout << maxDiff;

  return 0;
}

INOI 2016: Wealth Disparity

Input Format

Example

The answer is 199124525.

1 solution

0 pending reports