Editorial for Facebook Hacker Cup '15 Round 1 P4 - Corporate Gifting
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem is equivalent to the following graph theory formulation: given a tree with nodes, color the nodes with colors , such that no two adjacent nodes have the same color, and that the sum of all colors is minimal. Since a tree is a bipartite graph, it can be always be colored with two colors and , but this does not always yield the minimal solution as shown in the following simple example:
First, we need to construct the adjacency lists for each node. This can be achieved by using vectors or lists in order to use memory.
Assume that the number of different colors used in the minimal solution is . We can formulate a recursive solution (though note that this can also be computed bottom-up by removing leaves from the tree as we go).
For each node , let be the minimal sum of colors in the subtree rooted at node , given that is the color of node . Let be the children of . We can try any of the colors for the node , and compute as:
Therefore, direct implementation of the above method gives us a solution with time and memory complexity .
We can also prove that is an upper bound for . Let be the size of the smallest tree that needs all colors in an optimal coloring. Trivially, it holds that and . Without loss of generality, we can pick the node with color to be the root. In that case, the root needs to be adjacent to all colors from to and we can apply the inductive hypothesis as follows:
This completes the proof. The above algorithm therefore has complexity in both time and memory. We leave the problem of constructing a minimal tree that requires colors as an exercise for the reader.
However, there is also an algorithm with time and memory complexity. The above formula can be simplified if we just use the two best values for each node, together with the colors where these minimum values are achieved.
Let and be the best and second-best colors for the node respectively. Now,
This appears to still take time as we need to try all colors, leading to an solution. However, we can improve this to time. Let be our base cost, the minimum we must pay for the subtree rooted at :
Now, let be the additional cost if we decide to use color :
We can precompute in time, and then we can get the minimum cost of coloring 's subtree in time with:
And with that, our solution is now !