We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Process tree sizes in descending order (bigger trees will give a better maximum if processed first)
Consider the amount of handshakes needed to build each tree and the final friendship count of the tree (which will be added each succesive handshake which DOESN'T involve this tree).
Managed to solve it in Python 3 (my "standard fare" is C++) :)
The complexity of the solution is, I believe, O(m+log q + q) where q is the quantity of trees which were built (usually significantly smaller than m -> worst case q==m)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Value of Friendship
You are viewing a single comment's thread. Return to all comments →
Couple of hints (based on my solution):
Use disjoint sets to build a forest of trees.
Process tree sizes in descending order (bigger trees will give a better maximum if processed first)
Consider the amount of handshakes needed to build each tree and the final friendship count of the tree (which will be added each succesive handshake which DOESN'T involve this tree).
Managed to solve it in Python 3 (my "standard fare" is C++) :)
The complexity of the solution is, I believe, O(m+log q + q) where q is the quantity of trees which were built (usually significantly smaller than m -> worst case q==m)