Oh, No! You have been appointed as the organizer of Giggle, Inc.’s annual mandat

Question

Oh, No! You have been appointed as the organizer of Giggle, Inc.’s annual
mandatory holiday party! The employees at Giggle are organized into a strict hierarchy, that is, a tree with the
company president at the root. The all-knowing oracles in Human Resources have assigned a real number to
each employee measuring how “fun” the employee is. In order to keep things social, there is one restriction
on the guest list: an employee cannot attend the party if their immediate supervisor is also present. Give an
algorithm that makes a guest list for the party that maximizes the sum of the “fun” ratings of the guests.

Explanation / Answer

Modelling

1. We will model this problem in the form of tree i.e Employee of the Giggle Inc's annual will be the nodes of Tree.
2. The organizer of Giggle, Inc.’s  will be the root of the tree.
3. fun(employee) will give us the fun rating of the employee
4. We will calculate P(x) and Q(x) representing the optimal fun if the employee x is present or not present in the party

Scanario:

Consider an Supervisor L having three Employee under him {M, N, O}

1 . So if L is invited which means we cant invite M, N and O to the party. So the optimal solution will be
P(L) = fun(L) + Q(M) + Q(N)+ Q(O).
2 . So if L is not invited which means each of its children can be invited or not invited. So the optimal solution will be
P(L) = max { P(M) , Q(M) } + max { P(N) , Q(N } + max { P(O) , Q(O) }


ALGORITHM

MandatoryParty(a)

P(a) <-- fun(a)
Q(a) <--0
for all children b of a
   MandatoryParty(b) . // This will compute P(b) and Q(b)
  P(a) <-- P(a) + Q(b)
N(a) <-- N(a) + max {Q(b), P(b) }


Time Complexity:

For each internal node we spent time equal to its children and for leaf nodes we spend O(1) time , As we know the sum of degree of nodes is equal to n. So the time taken will be equal to O(N).

Space: To avoid recalculationg again and again we need to sabe P and Q values so for n nodes it will take O(N)

Thanks, let me know if there is anything u dint follow, or if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.