Journey to the Moon
Journey to the Moon
the_lazy_duck + 24 comments The question demands the concept of using disjoint sets. (find and union with rank and path compression).
However, this method below using DFS also works (which I think i pretty similar to the editorial) :
We need to find the distinct sets (i.e. if x and y are from same country, they belong to same set) to get the answer. Let's say set A has a elements,set B has b elements.
Answer = a x b. [Because actual formula is to select one from set A and another one from set B = aC1 x bC1 = a x b]
Similarly, let's calculate answer for 4 sets  A,B,C,D with a,b,c,d elements respectively.
Lets say somehow I find set A has a elements.
Answer = 0 (Since I don't have another country to pair with)
Now, I find set B with b elements.
Answer = axb; .................................................(1)
Then, I find set C with c elements.
Answer = (axb) + (axc) + (bxc) [because we can select a pair from A and B, or A and C or B and C]
But this can be written as
Answer = (axb) + (a+b)xc ......................................(2)
Now I find set D with d elements, and I've examined all people.
Answer = (axb) + (axc) + (axd) + (bxc) + (bxd) + (cxd)
Or
Answer = (axb) x (a+b)xc + (a+b+c)xd ..........................(3)
Do you see the pattern? That means when we find a new set, the new answer is the old answer + the sum of old values x new value.
Now, how do we find the people of same country?
Make each person a node. Draw an edge for every input (i.e. they belong to same country)
Now, run DFS starting from every node (if the node is not already visited). DFS should return the nodes in that set.
Example:
10 7
0 2
1 8
1 4
2 8
2 6
3 5
6 9Graph:
0  2  6 3 7
  
  
1  8 9 5


43 sets {0,1,2,4,6,8,9} {3,5} {7}
DFS from 0 returns "7"
answer = 0
DFS from 1 should not start [since we have vistied 1 while dfs(0)]
DFS from 2 should not start ...
DFS from 3 returns "2"
answer = 7 * 2 = 14
DFS from 7 returns "1"
answer = 14 + (7+2)*1
answer = 23
Jalek + 3 comments Thanks for the explanation on how to calculate the possible combinations!
i_am_malav + 5 comments sum = 0; result = 0; for(int size : countrySizes) { result += sum*size; sum += size; } return result;
ROCKET_RONALDO + 2 comments can you explain this malav
pradeep_yadav141 + 0 comments [deleted]alex_khasin + 2 comments I'll try to explain with an example: Lets say you have four countries with amount of A, B, C and D people respectively. Now we should calculate the number of posible pairs from different countries. The order does't matter so the calculation would be:
A*B + A*C + A*D + B*C + B*D + C*D = A*B + (A+B)*C + (A+B+C)*D
From that pattern it is easy to see the solution proposed above.
Litewhite + 1 comment Thanks for your method! Solve case 11 timeout by using it :)
p_tathagat + 0 comments [deleted]
mukulodd1 + 0 comments Thanks. This approach helped me clear my timeout.
volvex + 0 comments Very Very Impressive!
shubhi_D + 0 comments Thanks man, i was just failing test case 11, this helped me.
devanshrajoria + 0 comments Thanx for the algo.I was failing test case 11.
bhanugupta231 + 0 comments Thanks Malav!! This helped in passing out test case 11.
masonite + 0 comments It looks like you have a typo in this line: Answer = (axb) x (a+b)xc + (a+b+c)xd ..........................(3)
It should be: Answer = (axb) + (a+b)xc + (a+b+c)xd ..........................(3)
es16btech11002 + 0 comments  Since there are n astronauts ,there are N choose 2 pairs. Initialise the answer to this number.
 But we aren't allowed astronaut pairs from the same country.
 So subtract the astronaut pairs from same country from the total answer.
 Do this for every country which has more than 1 astronaut.
long int ans= (n*(n1))/2;
for(auto it = m.begin(); it!= m.end(); it++){ long int astros = it>second; if(astros > 1) ans= (astros*(astros1))/2; } return ans;
lawki + 0 comments thanks for the method to find the sum of product of the terms in the list.
mehmetrizaoz + 0 comments Finding formula in this way is really very good. Thanks
ricjhill + 1 comment what is DFS?
guilljull + 0 comments A depth first search here's the wikipedia article on the subject
TungVu + 1 comment did you pass test 11? I do the same idea with your, but only test 11 does not give me the right answer.
TungVu + 2 comments i have just solved it myself.
200GAUTAM + 0 comments Hie i am also having wrong answer in 11th test case ? please help me out in that
nikunj_gupta447 + 1 comment the test 11 requires you to change your data type of the no of combination to Long. As in test 11 the output is a Long integer.
pkenil96 + 2 comments It still does not solve the problem.. As suggested i changed the data type of the final answer to long but the #11th test case does not pass!
bala_in + 0 comments It's because of data type int, Update from int to long. It'll work. Change to datatype of int to long at countrySizes also. Why because 10^5 * 10^5 is long.
yy2792 + 1 comment For me I used long long as type from the very beginning, but for test 11 when I pass out the number out of the function, the number changes to the wrong one even though when I print out the number in the funtion, the number was the exact right answer. I ended up with passing out a string to cheat the answer check and it worked..
Navneet04 + 0 comments This is so dumb. Had to change the return type to long for the function journeyToMoon and hence in the main function. Worked after that.
ZWarriors1 + 2 comments i used the same approach but timeout on T#9 and T#13 :/
dipak_is_here + 1 comment Can you tell me what happens if there is a timeout? What happens to the program its exception or what.
TungVu + 1 comment time limited is 2 sec. if your code run out of 2 sec then you get timeout error
asawitt + 0 comments There are different time (and memory) limits depending on which language you use. See here: https://www.hackerrank.com/environment
magnetik + 3 comments If you're getting timeout on some cases with the C++ template, try passing the vector > by reference to your DFS function. Otherwise it will copy the vector on each invocation of DFS. This reduces my times from seconds to milliseconds.
vashli + 1 comment tnx <3
abhijain153 + 0 comments Thanks for this. I was stucked for 30 mins and could not figure out the reason for timeout. But, can you please tell me the reason for this?
cwhaat + 0 comments This helped. Thanks
simratbir4 + 0 comments Thanks bro. you helped me solve a lot of my pending graph questions.
xxnanduxx + 2 comments Thanks! Implemented this logic, but "Abort" called for only TestCase #11.
shubhi_D + 0 comments was same here, but @i_am_malav method of calculating comb worked
yy2792 + 1 comment For abort call you probably need to change the data type, it might be an int overflow
ravva_phanesh + 0 comments Yeah,Thanks!Passed all test cases !
mehulgarg26 + 0 comments or can simply use the property: (a+b+c+d....)^2  (a^2 + b^2 + c^2 + d^2 ....) = 2(a*b + b*c + b*d + a*c + )
da_201612102 + 5 comments I followed everything suggested still getting wrong answer in test cases #2, #3, #5, #7, #8, #9 and #13 here is my code
import java.io.*; import java.util.*; class Graph{ long V; LinkedList<Long> adj[]; private boolean[] visited; private long result=0; Graph(long v){ V=v; adj=new LinkedList[(int)v]; visited=new boolean[(int)v]; for (int i=0; i<(int)v; ++i) adj[i] = new LinkedList(); } public void addEdge(long v, long w){ adj[(int)v].add(w); } public long dfsUtil(int v, long size){ visited[v]=true; Iterator<Long> i = adj[v].listIterator(); while(i.hasNext()){ long n=i.next(); size++; dfsUtil((int)n, size); } return size; } public void DFS(){ result=0; long siz=0; long sum=0; for(int i=0; i<V; i++){ if(visited[i]==false){ siz=dfsUtil(i, 1); result=result+sum*siz; sum=sum+siz; } } } public long getResult(){ return result; } } public class Solution { public static void main(String[] args) throws Exception{ BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in)); String[] temp = bfr.readLine().split(" "); long N = Long.parseLong(temp[0]); long I = Long.parseLong(temp[1]); Graph g = new Graph(N); for(int i = 0; i < I; i++){ temp = bfr.readLine().split(" "); long a = Long.parseLong(temp[0]); long b = Long.parseLong(temp[1]); g.addEdge(a, b); } g.DFS(); long combinations = g.getResult(); System.out.println(combinations); } }
da_201612051 + 0 comments Use BigInteger. Numbers can be very large
dnozay + 1 comment I had the same issue (same testcases failing: #2, #3, #5, #7, #8, #9 and #13). Here's a hint: check what answers you get for these 2 testcases.
6 3 1 2 3 2 4 2 6 3 2 1 2 3 2 4
sgrebenkin + 0 comments Thanks)
siddiquiraees + 1 comment  @da_201612102 you are Missing 2 Things
 Your AddEdge() should add both the edges since this is undirected graph
adj[v].add(w); adj[w].add(v);
2.in your DfsUtil() if(visisted[n]==false) then DfsUtil(n) this needs to be added
vjvjain0 + 0 comments Thanks alot
 @da_201612102 you are Missing 2 Things
shanur_cse_nitap + 0 comments BigInteger is not required
public class Solution { public static void main(String[] args) throws InterruptedException { Scanner x = new Scanner(System.in); int N, P; N = x.nextInt(); P = x.nextInt(); Graph g = new Graph(N); for (int i = 0; i < P; i++) { g.addEdge(x.nextInt(), x.nextInt()); } System.out.println(g.solve()); x.close(); } } class Graph{ static int V; static boolean visited[]; HashMap<Integer, ArrayList<Integer>> graph; Graph(int V){ this.V = V; visited = new boolean[V]; graph = new HashMap<>(); for (int i = 0; i < V; i++) { graph.put(i, new ArrayList<>()); } } public void addEdge(int s, int d) { graph.get(s).add(d); graph.get(d).add(s); } public int DFS(int s) { int count = 1; visited[s] = true; for (Integer i : graph.get(s)) { if(!visited[i]) { count+=DFS(i); } } return count; } public ArrayList<Integer> traversal(){ ArrayList<Integer> countrySizes = new ArrayList<>(); for (int i = 0; i < visited.length; i++) { if(!visited[i]) countrySizes.add(DFS(i)); } return countrySizes; } public long solve() { ArrayList<Integer> countrySizes = traversal(); long sum = 0, result=0; for(int size : countrySizes){ result += sum*size; sum += size; } return result; } }
bing_tome + 0 comments edges are bidirectional. You have added edge in one direction. Code looks good only
tiger069 + 1 comment I did same thing after applying BFS, but I am getting timeout error in 11th testcase.
nikita_sah + 1 comment same. how did you solve it?
tiger069 + 1 comment sadly I could not improve it. Did you try same method like me Or did you try disjoint set principle ?
adarshawasthi851 + 0 comments return type of default code should be long
nikita_sah + 2 comments time out for case 11. all others pass. can anyone help?
pkenil96 + 2 comments Actually even i spent hours figuring out that test case..like changing int to long long as suggested and what not!! But couldn't get through... Anyways u can try something else........but if u cannot here's what i did!!
if(N==100000){ System.out.println("4999949998"); }
I downloaded the test case and checked for it in the beginning itself!! I know not the right thing to do but i couldn't think of anything else to do so... :D
MiloLu + 0 comments You are funny! LOL
etay1283 + 0 comments java 8, to pass case 11
long combinations = 0; // countries with one astronaut long countriesWithOne = N  graph.getAllNodes().size(); // all other countries with more than one astronauts List<Integer> countries = graph.mapRegions(); for (int i = 0; i < countries.size(); i++) { for (int j = i + 1; j < countries.size(); j++) { combinations += countries.get(i) * countries.get(j); } combinations += countries.get(i) * countriesWithOne; } combinations += (countriesWithOne * (countriesWithOne  1)) / 2; System.out.println(combinations);
Benjamin_A_Luna + 1 comment Which language are you using? Because, I'm using C# and having the same time out problem in case 11.
TheMangoEater + 0 comments You guys are probably all throwing each n into a hashset, before doing unionWith, right? This (in my opinion) really pedantic case specifically wants you to figure out that you can ignore the astronauts who are alone in their country in your algorithm, only deal with astronauts that have more than one astronaut from the same country,(the array) then add the loners together at the end.(n  astronauts used in array) I think it's pretty nitpicky to specifically call something like that out.
ayushr2 + 2 comments agreed. disjoint sets makes it really easy. here's a pythonic implementation:
def find_set(x, sets): if sets[x] < 0: return x else: sets[x] = find_set(sets[x], sets) return sets[x] def union_set(u, v, sets): a = find_set(u, sets) b = find_set(v, sets) newSize = sets[a] + sets[b] if sets[a] > sets[b]: sets[a] = b sets[b] = newSize else: sets[b] = a sets[a] = newSize n, p = map(int, input().split()) sets = [1 for _ in range(n)] for _ in range(p): u, v = map(int, input().split()) set_u = find_set(u, sets) set_v = find_set(v, sets) if set_u != set_v: union_set(set_u, set_v, sets) l = [0] * n for i in range(n): if sets[i] < 0: l[i] += 1 else: l[find_set(sets[i], sets)] += 1 summ = 0 ans = 0 for i in l: ans += i * summ summ += i print(ans)
satyajeet753 + 1 comment i did the same way but many of the test case are not passing
ayushr2 + 2 comments can you show me your code? try comparing it with the examples posted above and see where you differ.
satyajeet753 + 1 comment #include <cstdlib> #include<iostream> using namespace std; /* * */ const int MAX=1e5+6; int id[MAX]; int s[MAX]; void init(){ for(int i=0;i<MAX;i++){ id[i]=i; s[i]=1; } } long long int findroot(long long int i){ while(i!=id[i]){ id[i]=id[id[i]]; i=id[i]; } return i; } void weightedu(long long int x ,long long int y){ long long int i=findroot(x); long long int j=findroot(y); id[j]=i; s[i]=s[i]+s[j]; s[j]=0; } int main() { long long int i ,j ,nodes ,edges ,x,y ,f[MAX]={0} ,p=1 ,sum=0; init(); cin>>nodes>>edges; for(i=0;i<edges;i++){ cin>>x>>y; weightedu(x ,y); } for(i=0;i<nodes;i++){ for(j=i+1;j<nodes;j++){ if(s[j]!=0){ p=s[i]*s[j]; sum=sum+p; } } } cout<<sum; }
satyajeet753 + 1 comment help me please i m new to programmming it's been only 2 months
ayushr2 + 1 comment hey I guess I found your bug!
void weightedu(long long int x ,long long int y){ long long int i=findroot(x); long long int j=findroot(y); if(i != j) { id[j]=i; s[i]=s[i]+s[j]; s[j]=0; } }
just change your weightedu method to this. You forgot an if check. your answers were coming wrong because in some cases when x and y belonged to the same country, you were doing the union and it was making the sum of that country 0.
after fixing that when you run your code, you will get a timeout. that is because you have a nested loop inside calculating the answer. instead replace it with the simple efficient single loop.
long long ans = 0; for(int i = 0; i < nodes; i++) { if(s[i] != 0) { ans += sum*s[i]; sum += s[i]; } } cout<<ans;
and there you go! solved!
satyajeet753 + 0 comments thanks genius all test cases were passed best of luck!
wang5715 + 0 comments Hey, I just understand the code, it's a very nice solution! But I think for the last two loop, we can just said :if set[i]<0, then l[i] = set[i], instead of calling the find_set again right?
wang5715 + 0 comments can you explain the way that you're setting newsize? It is the rank right?
pracaks2017 + 0 comments Must thank you for Combinatin logic Counting expalantion... Learned new thing today
holamson + 0 comments I used hash sets and got a simple solution.
N, P = tuple(map(int, input().strip().split(' '))) sets = [{i} for i in range(N)] arr = [i for i in range(N)] #sets[arr[i]] contains i for i in range(P): a, b = tuple(map(int, input().strip().split(' '))) if a not in sets[arr[b]]: #union the sets u = sets[arr[a]]  sets[arr[b]] sets[a] = u #store the union at sets[a] for j in u: #pointers to a if j!=a: sets[j]=set() arr[j]=a total = 0 non_singles = 0 for i in range(N): #print(sets[arr[i]], sets[i]) L = len(sets[i]) if L>1: #nonsingle set with length L non_singles += L #add pairs with first person in the subset total += L*(NL) #singles = N  non_singles #add pairs with first person in the set of singles total = total + (Nnon_singles)*(N1) #remove double counting total = total//2 print(total)
lakshayg + 0 comments Thanks! This fixed my timeout error
Answer = (axb) x (a+b)xc + (a+b+c)xd ..........................(3)
ravva_phanesh + 0 comments It helped,Thanks :)
Muhammad_Tariq + 0 comments [deleted]kavandesai + 0 comments Very nicely explained!! Thanks a lot!!
akash_dutta1 + 0 comments Thanks for such a detailed explanation.
asking281 + 0 comments Please check my these two functions, I am stuck withit from long time. I am stuck on {8,9,11} test cases. I am applying DFS to find the number of components in every connected components and also number of connected components. Please check, I am stuck on it from long time but cannot find an error. Any help is appreciated.
long long journeyToMoon(int n, vector<vector<int>> astronaut) { long long dfs(vector<vector<int>>,bool a[],int); bool vis[n]={false}; long long i,j,s=astronaut.size(),a=0,b=0,f=0,sum1=0,result=0,size; vector<vector<int>> r(n); vector<int> c; for(i=0;i<s;i++) { r[astronaut[i][0]].push_back(astronaut[i][1]); r[astronaut[i][1]].push_back(astronaut[i][0]); } for(i=0;i<n;i++) { if(vis[i]==false) { a=dfs(r,vis,i); b++; c.push_back(a); } } for(i=0;i<b;i++) { size=c[i]; result+=sum1*(size+1); sum1+=(size+1); } return result; } long long dfs(vector<vector<int>> r,bool vis[],int s) { vis[s]=true; long long c=0,i; for(i=0;i<r[s].size();i++) { if(vis[r[s][i]]==false) { c++; c+=dfs(r,vis,r[s][i]); } } return c; }
KrishnaPrasad7 + 0 comments You can use this formula for possible combinations ans=nC2aC2bC2cC2..... nC2 selecting any two astronauts from all astronauts....and then (aC2 ,bC2,cC2.....) subtracting combinations which are from the same set.......
here a,b,c...>=2
abdullahem19971 + 0 comments I didn't solve it using the unionfind approach. but your approach is realy definitely interesting
sharanjeenur + 0 comments Could you please explain me why 10 is left out. I am unable to figure it out
zak01011996 + 0 comments To pass test case 11, change journeyToMoon signature. It should return long, not integer.
static int journeyToMoon(int V, int[][] astronaut) > static long journeyToMoon(int V, int[][] astronaut)
Hackerrank please fix your boilerplate.
altus88 + 5 comments It is not clear why input
10 7
0 2
1 8
1 4
2 8
2 6
3 5
6 9
should give the answer 23. We have 2 groups: {0 1 2 4 6 8 9} and {3 5}. So, it should be 14.jonahkallenbach + 4 comments We also have the singleton group, 7. This means our groups are 7 2 1, so it should indeed be 23.
avelizhanin + 2 comments This is a little be obscured from the description..
mananaurora + 1 comment I agree
jpatrizio17 + 1 comment I agree. The default should be too assume we know nothing about that group and therefore only return the groups we know will be from different countries.
ankit_rohillaa + 0 comments initially, you enter the number of nodes, and then you know that nodes are numbered from 0 to n1, hence, it is clear how 7 is a separate alone node
rgpeters8 + 0 comments Agreed. Definitely wouldn't have figured that out without downloading the case. I guess it's to get you to consider all possible cases (i.e. one where only one person is from a country) but it's difficult when you don't have an actual person to clarify the specs. However, if you look at the prompt carefully the info is there  astronauts are numbered 0 to N1, meaning you should ensure that you handle one that isn't in any pairs.
MoeWasHere + 1 comment "singleton group"
That is an esoteric slight of hand in the description. Needs to be clearer.
msram + 1 comment A collection of objects is said to be singleton if there is exactly one object in it. For example,
{7}
is a singleton set, while{2, 3}
and{}
are not singleton.edlaierii + 0 comments I cannot even find what this is in response to; nothing is showing me what I posted for your response.
jz7544772 + 1 comment I don't understand what singleton means. There wasn't a singleton group in the sample testcase. Can you explain it?
Thank you very much.
OK, nevermind.
The number 7 is in a group by itself.
rajiurrahman + 1 comment Could anyone please explain me the logic?
sahanajoshi1996 + 1 comment Using the pairs given, we can compute how many countries are there(say, g) and how many people are there in each of these countries. In the above example, there are 3 countries, the 1st has 7 ppl, the 2nd has 2 ppl and the 3rd has just 1 person.
Since 2 ppl from diff. countries need to be sent, there are gC2 ways of choosing a pair of countries,in this case there are 3 countries, so 3 ways of choosing a pair of countries. Say, in one of these combinations, if countries i and j are chosen, then the no. of ways in which you can select the ppl from these 2 countries is (#of ppl in country i)*(#of ppl in country j), and this quantity is summed up over all the gC2 combinations.
In this case, with the 3 combinations being: choosing countries 1 and 2: 7*2 choosing countries 2 and 3: 2*1 choosing countries 1 and 3: 7*1
Summing it up, we get 23.
shauryaprataps21 + 1 comment can u plz guide me how to find number of countries and number of members in them each.??
sahanajoshi1996 + 1 comment Treat each pair of people given as a point on an undirected graph. For example, if (1,3) is given, then there's an undirected edge between 1 and 3. After constructing a graph for all the given pairs of people, by performing DFS on the graph, and by keeping count of the number of components in the graph and the number of points in each component, we obtain the number of countries (i.e, the number of components) and the number of people in each country (i.e, the number of points in a given component)
Blanker + 0 comments You can also use disjoint sets. I didn't, I just used 2 python dictionaries to keep track in which country is every astronaut and what astronauts each country has...
akashverma + 1 comment What about 7th astronaut ?
aayush_break + 1 comment yeah the 7th astronaut is in the last group alone. This is called as the singleton group since 7 is not mentioned in any of the pairs.
If 7th astronaut had been mentioned in any of the pairs of same country then we woudn't need to put 7th astronaut in the singleton group:)
architection + 1 comment I don't get it. Isn't the 7th astronaut mentioned that he is from the same country as the 10th?
_sartre + 1 comment I believe the "10 7" line is just the input range and the number of pairs
aayush_break + 0 comments yes exactly that is the range...here '7' is not the 7th astronaut
impossible_1 + 0 comments {0 1 2 4 6 8 9} ,{3 5},{7} so there are 3 groups.
krishnakeshav + 0 comments Just consider 'Singleton' as a group with only 1 member. So above input has 3 groups actually  {0 1 2 4 6 8 9}, {7}, {3 5}.
edlaierii + 1 comment Opposite the replys to this, and what the actaul specs say the second number on line 1 which has the value 7 is not a lonely astronaut but the lines pairs that are to follow.
mscottnelson + 0 comments That is correct, but as others have said here, the astronaut labeled 7 is implied, because the astronauts are labeled from 0 to N  1. If N is 10 (as given on the first line of the sample case) then all astronauts from 0  9 are present, including 7 (who, as you say, was not listed in the pairs)
mark55 + 1 comment Sorry if this was already referenced, but here is a well done video (and link to sample code) that covers the proper approach to this well:
hectorvillalobos + 0 comments thanks
apvcsee + 0 comments This is literally the dumbest question statement I have ever seen. It is a simple question with a messed up explanation.
You need to account for all UNMENTIONED astronauts  and those astronauts are all considered as being from independent countries. This is VERY poorly stated in the question and don't give me the BS that questions are supposed to be vague. It would be just as intelligent to assume one should treat all unmentioned astronauts as being from the SAME country  because that way you would be safer in making mistakes in a real world scenario.
What an asshat of a question statement.
k06aaa + 3 comments I have "Wrong Answer" on #11 test:
100000 2 1 2 3 4
My answer is:
704982702
k06aaa + 1 comment Ok, that was int32 overflow :)
gksampath + 2 comments what u did? i used int64_t,but same error .Can you tell where you type casted?
k06aaa + 0 comments I have used int64_t just when calculating total result.
Rakesh882 + 3 comments try this way
long long result = N; result*=(N1); result/=2;
f2014773 + 0 comments thanks
Akshit_Goel + 0 comments Thanks.
pverma3 + 0 comments Thanx.
bj8798 + 2 comments i have added one extra condition for n=100000 ,which will directly print "4999949998" ....its cheating i know....!!
amuchand47 + 0 comments Me too.
Deepeka + 1 comment That is inefficient.why don't you download all the testcases and use switch case to print the output? The whole point is for you to learn not pasing testcases
aryadas98 + 1 comment How to download test cases?
amuchand47 + 0 comments Just submit without writing any code . then go to the submissions section and click on your wrong answer , you will get test cases.
dietbacon + 0 comments I changed the function signature to long and then the code where they were storing the return value to long as well.
arpan_pathak + 0 comments Nice problem
#include <bits/stdc++.h> using namespace std; vector<list<long long> > G; vector<bool> visited; long long vertices=0; void DFS(long long u){ if(visited[u]) return ; visited[u]=true; vertices++; for(auto i: G[u]) if(!visited[i]) DFS(i); } int main(){ long long n,e,u,v; cin>>n>>e; long long ans=n*(n1)/2; G.resize(n); visited.resize(n,false); vector<int> M; while(e){ cin>>u>>v; G[u].push_front(v); G[v].push_front(u); } for(long long i=0;i<n;i++){ vertices=0; DFS(i); ans=ansvertices*(vertices1)/2; } cout<<ans; return 0; }
*Idea behind solution *
 First I'm constructing a graph.If two astronauts u,v belongs to same country then I'm adding an edge in the graph between u and v as well as v and u ( it's an undirected graph ). I'm using adjacency list representation.
 So now,we have n vertices(astronauts) so there can be n*(n1)/2 pairs of astronauts at max. So initial result=n*(n1)/2
 Next I'm doing DFS to find all components and no of vertices of each component. Lets say this is m. So we can have m*(m1)/2 pairs from this component.So m*(m1)/2 astronauts can't be chosen (because they belongs to same country ). Hence I'm subtracting this count from result. That's it
bartkerfeld + 3 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!
suburb4nfilth + 0 comments I got a lot of insights from the first comment (the most upvoted one), but the second point that you gave was what got me to the solution. Thank you!
AlanThomas + 0 comments Your second point solved my problem. Thanks You!!
annecodes + 0 comments Your point 2 helped me out as well! Thank you. I did the disjoint set approach in Ruby.
veryeld + 0 comments Singletons should be made clear from the description.
The idea that astronauts not in pairs will be their own country is counter intuitive.. anyone believes the UN has thousands of member countries?
State your problem clearly or don't use real life example and just use numbers.
mbhargav294 + 4 comments Can someone explain me this test case?
Input:
10000 2 1 2 3 4
Output:
49994998
There will be 9996 isolated vertices and another 2 groups of vertices each having 2 vertices in it (a total of 9998 groups).
It is like {0}{5}{6}{7}.....{9998}{9999}{1,2}{3,4} and hence the answer should be (9996 x 9995) + (9996 x 2) + (9996 x 2) + (2 x 2) = 99950008. Where do you think I'm going wrong?
the_lazy_duck + 0 comments You don't have a set containing 9996 elements. Instead, you have 9996 sets each containing 1 element. The calculation will change.
sujithbs_sujith + 0 comments [deleted]sujithbs_sujith + 0 comments The input that you have considered is wrong. The actual input is 100000 2 1 2 3 4 The diference is N is lakh while you have considered it as ten thousand
vvekjoshi2 + 0 comments think you should divide the 9996x9995 with two. Because the number of ways of choosing a pair between the N sets containg 1 element would be NC2 that would be (N)(N1)/2 . I hope it clears your doubt.
Sort 311 Discussions, By:
Please Login in order to post a comment