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.
Like a few others have mentioned, I was also stuck with getting getting test case 11 to not timeout. I solved this problem in two different ways: 1) using disjoint sets and 2) using dfs and a graph. Both of these approach can be made to work fast enough for case 11 (assuming you have a decent implementation).
The problem for me was in how efficient I was using the sizes of each connected component. The idea I came up with which passed the case worked as follows:
1) I constructed a list of all the component sizes. For example, the provided test case would give me the list {2, 2} since (0,1) and (2,3) are the components. This can be constructed in O(V + E) time.
2) I iterated through these sizes. Notice that each astronaut in a component can pair with any astronaut not in the same component (i.e. the other N - size) astronauts giving you a total of size * (N - size) pairs involving the first component astronauts. Add this to your total and repeat. You will have to be clever for later components to avoid repeated counting. You can do it, good luck!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Journey to the Moon
You are viewing a single comment's thread. Return to all comments →
Like a few others have mentioned, I was also stuck with getting getting test case 11 to not timeout. I solved this problem in two different ways: 1) using disjoint sets and 2) using dfs and a graph. Both of these approach can be made to work fast enough for case 11 (assuming you have a decent implementation).
The problem for me was in how efficient I was using the sizes of each connected component. The idea I came up with which passed the case worked as follows:
1) I constructed a list of all the component sizes. For example, the provided test case would give me the list {2, 2} since (0,1) and (2,3) are the components. This can be constructed in O(V + E) time.
2) I iterated through these sizes. Notice that each astronaut in a component can pair with any astronaut not in the same component (i.e. the other N - size) astronauts giving you a total of size * (N - size) pairs involving the first component astronauts. Add this to your total and repeat. You will have to be clever for later components to avoid repeated counting. You can do it, good luck!