2
$\begingroup$

I was recently asked this problem in an interview and I couldn't solve it. Need some help on how to solve this problem.

Given a K-ary tree with N nodes (N <= 2000 and K <= 12) you need to assign some colour to each node.

Also, each node has a value associated with it which is equal to the number of units of paint required to color it (this value is <= X (defined below) ).

Now you have an infinite number of bucket of paints each having different color available to buy but a fixed capacity of 'X' units which is same for each bucket (X <= 30).

Also there is a constraint that you can only choose a node for coloring once all nodes lying on the path from root of the tree to this particular node have been colored so you always have to start coloring from the root and then proceed.

The buying operation is sequential (You only buy the next paint bucket once you have completely used the previous).

Also each node should be completely colored with one color only. So, if you choose a bucket of paint and color a node using some units of paint from that bucket and there is no available node satisfying the constraint which you can color using the remaining paint from that bucket, then you will have to throw this bucket and buy the next bucket of paint for the next node.

You need to find out the minimum number of cans of paint that you will have to buy to color all nodes of this tree.

The best possible solution that I could think of was doing a DP with a bitmask as a state that denotes the nodes that I've not chosen so far but that has an asymptotic complexity of O(2^N * N) which is too slow for the given values of N. Can somebody think of a solution that works for the given constraints?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! What approaches have you considered? What are your thoughts? We're happy to help you understand the concepts but just handing you a solution is unlikely to achieve that. It's helpful to see how you've approached it and what thoughts you've had already; that helps give more useful answers. Have you tried writing a recursive algorithm? Have you tried dynamic programming? You might find this page helpful in improving your question. $\endgroup$ – D.W.♦ Mar 11 '17 at 23:38
  • $\begingroup$ @D.W. - Edited. $\endgroup$ – Gena Mar 12 '17 at 7:08
  • $\begingroup$ If K were not bounded, then even if the input tree is restricted to have depth 1 (that is, there's a root, and every other vertex is a leaf) then this is already equivalent to Bin Packing, which is NP-hard. (Cans of paint are bins.) Also I'm not sure how the "must paint vertices closer to the root first" constraint actually changes anything -- renumbering the cans turns any solution that violates this rule into one that doesn't, without changing the total number of cans used. $\endgroup$ – j_random_hacker Mar 12 '17 at 14:14
  • $\begingroup$ The constraint does change the problem since you only buy the next paint bucket once you have used the previous. So, you cannot for example, paint the leaf node directly after the root using the same bucket. $\endgroup$ – Gena Mar 13 '17 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.