PROBLEM LINK:Author: Roman Rubanenko DIFFICULTY:Medium PREREQUISITES:Bitwise operations PROBLEM:Find out number of pairs of vertices u, v which are connected to each other not directly by an edge but by another vertex w such that w is a neighbour of both u and v. ExplanationNOTE: I have done a slight experiment in the editorial. The editorial is presented as a process of two persons asking each other questions and solving the problem with help of each other. First person's words are written in italic while that of second are in normal text. Hey, I am not able to figure out anything. What is the trivial algorithm that I can have here? As n <= 2000. O(n^3) is a trivial algorithm. For each pair of vertices u, v not having an edge between them, we will find the vertices which are neighbour of both u and v. Let set neigh[u] denotes the neighbours of u except v. Similarly set neigh[v] denotes of v except u. Checking whether u and v are connected is same as checking whether intersection of set neigh[u] and neigh[v] is empty or not. We can implement this intersection step in O(n) easily. Oh, yes, I got it. Can we do it faster? Yes, Note that for each set neigh[v], we need to maintain binary n values, i^th of them represents whether the vertex u have an edge with vertex v. Can we make use of the fact that the values in the set are binary, can we somehow reduce the size of set and represent the information more succinctly?. Yes, As each of the value is binary, we can store them ceil(n / 32) groups where each group is of integer data type. Note that we are here making use of bits to encode the information of set in compressed form. Note the size of each set will reduce by a factor of 32 (as integer data type has size 4 bytes = 32 bits). Now you need to check whether two sets intersect or not. I think that we can make use of bitwise operations for this. Yes, Finding whether intersection of sets represented by two integers x and y is empty or not, can be done by checking their bitwise AND. If their bitwise AND is nonzero, they have an intersection, otherwise not. Few Small Points
Complexity: O((n^3) / 32), For each u, v we are having n / 32 sets. Intersection of two integers x, y can be find in constanct time because we can assume that bitwise operations are almost constant time opertions. So overall time complexity will n * n * n / 32 = n ^{ 3 } / 32. ANOTHER SOLUTIONLet us try to think in terms of powers of adjacency matrices. I think it can help us. What does i,j th element of powers of adjacency matrix denote? As the entries of the adjacency matrix gives you the connections between the vertices. If you take powers of adjacency matrix, then you are really combining the walks. So the i,j th entry of the k^th power of the adjacency matrix tells you the number of walks of length k from vertex i to vertex j. I understood it, but Where is the proof? You can prove it using induction. To form a walk of length k+1 from vertex i to j, you must first have a walk of length k from vertex i to some vertex v and then a walk of length 1 from vertex v to vertex j. Now relate these terms with matrix powers and you are done :) How can powers help me here? I am not able to exactly formulate this. You can note that i, j th entry of square of adjacency matrix will denote the number of walks of length 2 from vertex i to vertex j. So you can notice that if i,j the entry is nonzero, then we can say that vertex i and j are connected with each other by another vertex w. I can do the matrix multiplication of two square matrices of dimension n in O(n^3) time, which will get TLE, do you have some faster algorithm?? Well, there is an algorithm called Strassen_algorithm which can solve the problem in O(n ^{ log 2 7 }). Yes, that's cool. :) In our case, the matirces are boolean matrices, can we somehow compute their product faster? Fortunately Yes, there is a technique called Method of Four Russians which will help us. AUTHOR'S and TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 21 Jul '14, 01:03
showing 5 of 10
show all

Here is a clever O(N^3) solution which got AC.! I thought of something similar but didn't code it, as i thought it would run out of time..!! http://www.codechef.com/viewsolution/4359971 Obviously this solution should give TLE for a really strong test case. answered 21 Jul '14, 01:45

Not really... using long and checking for only lower indices, the operations can be reduced to (n)(n)(n1)/((64)*(2))=6.25X10^7 operations...That falls well within the time limit. answered 21 Jul '14, 11:23

I tried solving this using two approaches. One using Union_Find algo and another by making graph and doing dfs on each node as the constraints were small. but both failed giving WA :( Can someone who has used either of same approach tell where I went wrong?? answered 21 Jul '14, 01:10
2
consider 1 and 2 to be friend 2 and 3 to be friend and 3 and 4 to be friend then 1 and 4 does not have any mutual friends as friend of 1 is 2 and friend of 4 is 3.
(21 Jul '14, 01:15)
@subway I got my mistake. thanx :)
(21 Jul '14, 01:20)

can anyone tell me where my solution is wrong . sol : http://www.codechef.com/viewsolution/4359430 answered 21 Jul '14, 01:14

Hey,I used approach where i used bfs from each node and counted all those vertices with distance 2 from that node and marked them.did this for all vertices and counted total such pairs http://www.codechef.com/viewsolution/4359320 I got runtime error can any1 tell me why? answered 21 Jul '14, 01:20
1
Runtime error! N is at most 1000.I don't think so!!!
(21 Jul '14, 01:55)
i got runtime error dont know why!.Is the solution correct?
(21 Jul '14, 02:00)
I tried your code for small tricky test cases involving cycles.. works good for them. But when I changed all 1000values to 2000values (since n<=2000 and not <=1000), it gets a TLE.
(21 Jul '14, 02:20)
tnx got my mistake :)
(21 Jul '14, 02:46)
hey I just tried it the same way, getting WA though :(
(21 Jul '14, 02:48)

why does dfs fail in this? answered 21 Jul '14, 01:21
1
Because dfs counts people without mutual friends as well. dfs just assures there is a path but here we need path of length 2.
(21 Jul '14, 15:28)
http://www.codechef.com/viewsolution/4360176 i have used distance 2 in this ques. I am getting WA in this.
(21 Jul '14, 22:28)

I tried it using BFS also, here's my approach
which means the count the pair of nodes next to nodes which are adjacent to any node. but this still failed giving another WA :( somebody please correct where I am going wrong again !!
link
This answer is marked "community wiki".
answered 21 Jul '14, 02:46
Between each BFS, you might switch from one CC (connected component) of the graph to another, effectively not reaching friends that you did on previous iterations. The value of level[] for these friends will remain the same, and thus you might increase the value of ans incorrectly. Anyway, the approach is too slow and even after the correction you'll get TLE.
(21 Jul '14, 02:56)
@alexpizarroj could you/someone else just have a look at this submission and tell why this got TLE'd ??
(21 Jul '14, 03:07)
1
In the worst case, everybody will be friends with everyone. Thus, we'll have V=n and E approximately equal to n^2. BFS's complexity is O(V+E) which gives us O(n^2). Since you're running it from every friend, you end up with O(n^3), which is way too much. I must add: author's solution is O(n^3) too, but is has a very small constant factor which results from using bitwise operations wisely.
(21 Jul '14, 03:18)
I got it, the worst case :O thanx again @alexpizarroj :)
(21 Jul '14, 03:25)

Here are solutions both in JAVA and C++. Both of them use BitSet concept. I'll try and write this in terms for even a layman to understand. If you're a beginner, i'm assuming you know what the '&' bitwise operator returns for 2 binary values. If you don't then just google it. It's pretty easy C++:
My C++ submission: http://www.codechef.com/viewsolution/6843913 JAVA: Same concept. Its gets much easier here.JAVA has an awesome 'Bitset.intersects(BitSet)' method. Intersect means that they have atleast one common bit set. 1.Create an ArrayList of Bitsets and build the graph up. 2.Now same. run a loop for each vertex to check for non adjacent vertices. After that, simply check when (i!=j && !gr.get(i).get(j)) > if(gr.get(i).intersects(gr.get(j))), ans++; CAUTION: the second .get(j) is a bitset method. Not the arrayList one. It checks if the bit is set at position j DONE! My JAVA submission: http://www.codechef.com/viewsolution/6843885 Meanwhile, i'm picking up some of my old WA and TLE submission and try and make a few optimisations here :D answered 06 May '15, 23:13
It seems my optimisations were correct!! Cuts the runtime by HALF :D Here is my submission. I'll leave it to you to understand why this works :). Common sense actually :P
(06 May '15, 23:21)
Here's a similar SPOJ question I had solved. It's easier than this. I just used HashMaps there. http://www.spoj.com/problems/FACEFRND/
(06 May '15, 23:34)

Here's my approach. Plz help me find the flaw.
For example: 1 is connected to 2 and 3 4 is connected to 5 and 6 So we have 2 connected components with size 3 and 3. [{1,2,3}, {4,5,6}] Step 4 will go like this. For 1st component: 3  2  1 = 0 3  1  1 = 1 3  1  1 = 1 Total > 2 Same for 2nd component, hence Total suggestions will be 2 + 2 = 4 What is the problem in this approach? Please suggest. answered 21 Jul '14, 02:08
1
Consider the following example with 5 friends: 1>2, 1>3, 2>4, 3>5. The expected answer is 6, while your algorithm gives 12. a) 2 and 3 are not friends, but they have friend 1 in common. b) 4 and 1 are not friends, but they have friend 2 in common. c) 5 and 1 are not friends, but they have friend 3 in common. The issue with your approach is that you only get the sum of the number of indirectly connected friends in the CC (for every friend), and that doesn't help us at all to compute the desired answer.
(21 Jul '14, 02:23)
@alexpizarroj just to correct, the answer to your case is 6 not 3. the relationship is mutual, if 1 is friend of 3 then 3 is also friend of 1.
(21 Jul '14, 02:35)
@chandan721 you're right, I will edit my answer.
(21 Jul '14, 02:46)
@alexpizarroj : Thanks. I guess I misunderstood the problem. I was thinking that we can make suggestions to everyone in a cc who are not directly connected. Instead we need to target just the nodes which are at a distance of 2. Correct me if I am wrong.
(21 Jul '14, 14:40)
Maybe if you read the comments and saw that I asked that question...
(21 Jul '14, 16:04)

Seeing authors solution , I think wouldn't it be easier if we just use C++ bitset ? which supports the operation . I am getting WA though here answered 21 Jul '14, 03:04
1
have a look here... it's a sweet simple and efficient use of bitset<>
(21 Jul '14, 03:10)
can you explain a bit more what have you done inside the loop ? I mean , you just copied the whole bitset b[i] into cur ? why did you do that?
(21 Jul '14, 03:22)
1
@tamimcsedu actually the above one is not my solution. and there is indeed no use of 'cur' I just got AC using the same approach, I have also put some comments along with code for more understanding.. check out..
(21 Jul '14, 04:08)
Can you explain it, please?
(21 Jul '14, 04:45)

What is wrong with my code: http://www.codechef.com/viewsolution/4355232 ?? i expected that it will give TLE, but it gives WA. answered 21 Jul '14, 04:07
1
you're counting the resp in the wrong place. try this test case: 4 0011 0011 1100 1100 It should output "2", but your code outputs "4". Try changing "resp++" to "resp+=2" and breaking the third loop after the first valid "resp+=2"
(21 Jul '14, 06:46)
Thanks! I am idiot....
(21 Jul '14, 07:48)
2
@caioaao. Can you explain how the output is 2. According to me, it should be 4. 1 receives request from 2. 2 receives request from 1. 3 receives request from 4. 4 receives request from 3.
(21 Jul '14, 09:34)
ohh, sorry. wrong copypaste lol. this one should be 4. The one that should be 2 is this one: 4 0111 1011 1100 1100
(21 Jul '14, 16:05)

seriously thought of strassen's algorithm but dropped the idea thinking it wont work...damn !! answered 21 Jul '14, 04:29

My unfinished code is given below:
The code finds mutual friends; however, if A and B are already friends and share common friends, total is increased by 1,which is unwanted. I am at a loss at how to implement this condition efficiently; furthermore, the editorial does not explain how to do this either. What is the best way to include this restriction? Thanks, minimario answered 21 Jul '14, 05:51
keep an adjacency matrix so you can check if A and B are friends in O(1)
(21 Jul '14, 06:49)
Can you provide some code for that? Thanks!
(21 Jul '14, 07:00)
Take a look at my code: http://www.codechef.com/viewsolution/4361047 AdjMatN is the adjacency matrix in this case. it's just a copy of the input.
(21 Jul '14, 07:05)
I used bitwise operators as well as the adjacency matrix; however, I am still receiving a TLE... any way to improve further?
(21 Jul '14, 07:47)
well, I guess this problem has a strict time limit for python (but then again, I'm no expert in python). this is the optimized code that is equivalent to what I've done in C++: http://www.codechef.com/viewsolution/4362878 i've seen one solution that uses python and got AC, here it is: http://www.codechef.com/viewsolution/4360214 from this AC sol in python, it seems your issue is in slow I/O
(21 Jul '14, 18:17)
Yes; that was the problem. However, this problem was quite biased against Python users IMO; did users in other languages experience the same problem?
(22 Jul '14, 04:00)
nop, using slow I/O in C++ gives AC: http://www.codechef.com/viewsolution/4364866
(22 Jul '14, 06:19)
showing 5 of 7
show all

Complexity can be reduced to nn(n1)/128. The denominator comes from 64 and 2. Use long instead of int. Using symmetry, we compare each element only with lower indexed users. That's 1+2+...+n1=n(n1)/2. We do this n times. This takes 6.25*10^7 operations, well within time constraints. answered 21 Jul '14, 08:32

nice tutorial :) but can someone help me how to solve with strassens matrix multiplication. Can i get a code for implementing it?? answered 21 Jul '14, 15:55

I solved it using binary search. Firstly I stored all the pairs which were not friends together as a pair in a vector. Then I checked if both of these person have any common friend , by binary search . If yes , ans += 2 . My code : http://www.codechef.com/viewsolution/4354669 Elegant and Simple . answered 21 Jul '14, 22:13
1
No, your solution is O(N^3 log(N))  for each disconnected pair, you can end up checking all edges from one of them (you're not doing one binseatch, you're doing up to degree(u) binsearches) before breaking, and there can be a lot of them. It just has a really good constant and it's hard to make testcases where it runs worstcase.
(21 Jul '14, 23:54)

http://www.codechef.com/viewsolution/4360176 please I need why this codes fails. answered 21 Jul '14, 22:28

quality & timing of editorials have seriously improved on codechef..nic work answered 24 Jul '14, 21:57

here is my solutionhttps://ideone.com/i2Hw32. can any tell why it is showing wrong answer!! answered 26 Sep '18, 14:29

can we solve it using Disjoint sets concept
I have to say i love the idea of 2 persons interacting with each in the editorial. Amazing stuff!!
is O((n^3) / 32) fast enough to get AC? how much operations do your servers do per second? where can I see the specs of the cpu?
Nice Solution, but could you explain the Strassen_algorithm, I got the idea of squaring the matrix but could code the matrix multiplication part.
Nice way to present the solution (y) @dpraveen
is there any solution(solved) using the other method using matrix multiplication??
Can be solved using binary search . Complexity nnlog(n*n)
alphaparticle: No, your solution is O(N^3 log(N))  for each disconnected pair, you can end up checking all edges from one of them before breaking, and there can be a lot of them. It just has a really good constant and it's hard to make testcases where it runs worstcase.
is Strassen algorithm really fast enough to solve this? http://discuss.codechef.com/questions/48384/strassenalgorithmnotfastenough
The editorials of codechef are a lot more exhaustive and easier to understand than that of codeforces.