@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.
I tried it using BFS also, hereās my approach
-
Build an undirected graph of adjacency list using the matrix
-
then performed BFS for each node
-
In each BFS I keep track of levels of nodes, say if I start my BFS on node 1, then node 1 is on level 0 and all nodes adjacent to node 1 are on level 1 and so-onā¦
-
after doing all this for each node, I just counted all the nodes which are at level 2, LEVEL 2 because as described in the problem statement above, we need to
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.
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 !!
1 Like
tnx got my mistake 
hey I just tried it the same way, getting WA though
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.
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
@alexpizarroj could you/someone else just have a look at this submission and tell why this got TLEād ??
have a look hereā¦
itās a sweet simple and efficient use of bitset<>
1 Like
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.
1 Like
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?
What is wrong with my code: http://www.codechef.com/viewsolution/4355232 ?? i expected that it will give TLE, but it gives WA.
@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ā¦
1 Like
seriously thought of strassenās algorithm but dropped the idea thinking it wont workā¦damn !!
Can you explain it, please?
My unfinished code is given below:
sa=int(input())
flist=[int(input(), 2) for t in range(sa)]
total=0 for i in range(sa-1):
for j in range(i+1, sa):
if flist[i]&flist[j]!=0:
total+=1
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
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ā
1 Like
keep an adjacency matrix so you can check if A and B are friends in O(1)
Can you provide some code for that?
Thanks!