Last weekend (March 1-2) the 2014 HackerRank 101 Hack took place. In particular, a problem named Coloring Tree was present. Basically, the problem gives you a tree where each vertex is assigned a color and asks you queries where you have to find the number of distinct colors in a particular subtree.
My approach was to compute the number of distinct colors for every subtree using a DFS traverse of the tree. My algorithm went through the tree, and for every vertex it computed a set (
std::set) of all the distinct elements within its subtree. I accomplished this for every vertex using the following steps:
- Compute the sets for each of the children of the current vertex.
- Merge the children together by inserting all elements of the child sets within the subtree into the set of the largest child. (NOTE: Do not copy the set of the largest child. Simply insert the rest of the elements such that the number of insertions is
- Record the size of the merged set.
I accomplished this in my code through the use of an array of sets, and keeping pointers to the "active set" of a vertex, thus avoiding copying the largest child.
Here is my code on Ideone: http://ideone.com/Lje1R5
Now, onto my actual question. The reason I used this technique is because I remembered a similar technique from a past USACO problem. The USACO problem explained that the complexity of such a merging is O(nlog2n), if I understood it correctly. However, it did not provide a proof of the complexity. I've tried to deduce it on my own with induction, but am stuck on analyzing the merge step, since it involves the size of the largest subtree. I thought of maybe using something like Jensen's inequality to bound the sum of the subtrees, but wasn't able to get very far do too my inexperience with Jensen's. I am pretty sure the complexity is around O(nlog2n) because of my program's runtime: Runtimes (unless they had extremely weak test data?) My question is, how can such a complexity be deduced?