Question: Tiktok Singapore | Frontend Engineer 1
Entering edit mode


Click here to Practice

Tree Decrements


Q1 Part 2


5 Questions ( 2 MCQ + 3 Coding Questions ) MCQs were based on CSRF attack & diff between ArrayList & LinkedList.

Coding Q.1 => 2 Pointer Question Easy Q.2 => Minimum Swaps required to Sort an array Q.3 => Minimum time to complete all processes if at a particular instant we can have infinite computing capacity.

ADD COMMENTlink 25 days ago pushpendra.hpx2001 • 20 • updated 24 days ago Ayush Gangwani 510
Entering edit mode

Solution to Tree Decrements

First we make some observations:

Claim: Each node will be involved in atmost one decrement operation that is operated on two different nodes in an optimal solution.

Proof: Lets assume that node x is involved in two such operations. Then we have the following two cases:

  • It is involved with the same node (say y) in both the operations. Then we can always perform the decrement operations on node x and node y separately (i.e. we decrease the values of x and y by 2 separately) with a cost of 0 which is strictly better.
  • It is involved with two different nodes (say y and z) in the operations. Then we can notice that dist(y,z) <= dist(x,y) + dist(x,z). Hence we can decrease the value of node x by 2 separately and perform an operation on node y and node z for a cost of dist(y,z) which is either better or the same.

Thus it makes sense to decrease even valued nodes to 0 by performing the operation on themselves while perform exactly one operation for odd valued nodes. Since it is given that there always exists a solution, the odd numbered values must pair up (i.e. they must be even). So now we have reduced the problem to an easier problem --- "Given a tree and some special nodes, we have to find the minimum cost to pair up the special nodes such that the cost of pairing is equal to distance between two nodes."

Now to solve this, we can add the contribution of each edge in the answer, i.e., if we can determine the number of pairs for which a certain edge will be involved, we can find out the answer by summing the contribution for all the edges. Now notice that an edge will be involved in a pairing if and only if the subtree corresponding to it contains an odd number of special nodes. Thus we can find the contribution of each in a single DFS and calculate the ans in a time complexity of O(N).

ADD COMMENTlink 24 days ago Ayush Gangwani 510

Login before adding your answer.

Similar Posts
Loading Similar Posts