CODEWITHSUNDEEP
algorithmmathtreehierarchydynamic-programming
Agir Mahad
Agir Mahad

Reputation: 85

Best Algorithm to Invite People to Party

I'm new here, but have question found in my text book. Unfortunately it has no answers so I was wondering if someone could please help. The question is:

You are given the task of spreading invitations within a company. You only have the time to talk to a certain amount of people, but you are guaranteed that if you invite somebody, they will invite their boss, that person will invite their boss, and so on, all the way up to the CEO. You have mapped out the entire company hierarchy, and assigned a value to each person, indicating how valuable it would be to invite them. Given this setup and a limit on the number of people you can speak with, you want to compute the optimal set of people to invite. An optimal set of people will maximize the total value of all persons invited, directly or indirectly, by your selection.

There will be exactly one person, the CEO, with no boss in the hierarchy. All other people will eventually answer to this person on the command chain, but not necessarily directly.

You are guaranteed that each person will have at most one boss, but that boss may have another in turn. For example, person A may have a boss B, whose boss is C, whose boss is D, whose boss is the CEO. Thus influencing person A will automatically influence B, C, D, and the CEO.

Different employees may have bosses in common in the command chain. You DO NOT obtain additional value for influencing a person more than once. For example, if A and B both answer directly to the CEO, and you influence both, you will receive a value of val(A)+val(B)+val(CEO), not val(A)+val(B)+2val(CEO).

Given a positive integer j, select the j people that will ultimately result in the greatest overall value.

I know that the brute force approach is to just search the list for the max value j times, but that is not very helpful. I think there is a dynamic programming approach but my attempt did not always provide the correct answer. Any help would be appreciated!

Upvotes: 7

Views: 2661

Answers (3)

arghbleargh
arghbleargh

Reputation: 3170

Edit: this answer assumes the values for inviting people are all non-negative.

This problem can be solved using a greedy algorithm. Let us first discuss the case where the values are all equal, so we are just trying to invite the maximum number of people. The key observation is that in any optimal solution, you should always pick the person with the largest number of direct or indirect superiors. Here's a brief explanation of why: suppose person X has the most superiors, and you have some selections that don't include person X. Consider the person Y among your selections which shares the most superiors with X. Then, you can do better by selecting X instead of Y.

So in the first step, we can always greedily select the person with the most superiors. Then, the problem reduces to the same problem on several smaller trees. For example, suppose we are selecting 3 invitees from the following tree:

       A
   B       C
 D   E   F   G
H I J K L M N O

Our first selection will be H, which automatically gives us D, B, and A. Then, it remains to select 2 from the three trees

I   E      C
   J K   F   G
        L M N O

The next best choice is L, and so on.

We can do this efficiently, because we just need to keep track of the deepest child (not necessarily direct child) of each node, which we can compute beforehand. Then, we need some kind of priority queue data structure to select the best tree to pick from. If you are selecting k people from a hierarchy of size n, this should give a O(n + k log n) algorithm.

To extend this to the case where values may be unequal, basically the exact same idea works, except instead of depth, you need to calculate the total value of all superiors. For each node X, you keep track of the child Y which has the largest total value along the path between Y and X.

Upvotes: 1

smac89
smac89

Reputation: 43206

Sounds like a graph problem. You can use the idea of connected components to realise a solution to this.

  • First iteration will cover everyone in the company where you will determine who the CEO is and who is directly below him.
  • Take each of the bosses directly below the CEO as the initial set of components.
  • Then for each other person, you will use dfs to associate them with a 2nd level boss (This is the dynamic approach).
  • You want to do this last part in such a way that if person F is the boss of person E, who in turn is the boss of person D, ... all the way down to person A, then you want after the dfs to be able to say in O(1) time that person F is the boss of person A and vice versa.

Remember to keep a count for each boss where the count will be the sum of the values of all persons below him, and optionally keep track of the number of people.

The optimal case would be that you find all people lower in chain first, otherwise the algorithm should run in O(nk) where k is the maximum chain from bottom to top

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65498

Let V[e, k] be the maximum value of issuing k invitations to e and e's direct and indirect subordinates, ignoring the value of all direct and indirect supervisors of e. If employee e has no subordinates, then the base case is

V[e, k], k = 0 = 0
V[e, k], k > 0 = val(e).

If employee e0 has two subordinates, e1 and e2, then the recurrence is

V[e0, k], k = 0 = 0
V[e0, k], k > 0 = max over j of val(e0) + V[e1, j] + V[e2, k - j].

The naive convolution with more than two employees is too slow, so we have to convolve the first pair and then convolve in the rest. I'm going to omit the details.

Upvotes: 5

Related Questions