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.
2 Likes
I have to say i love the idea of 2 persons interacting with each in the editorial. Amazing stuff!!
6 Likes
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?
1 Like
Runtime error!
N is at most 1000.I don’t think so!!!
1 Like
Nice Solution, but could you explain the Strassen_algorithm, I got the idea of squaring the matrix but could code the matrix multiplication part.
i got runtime error dont know why!.Is the solution correct?
It depends on the type of operation. In this case, we are just using bitwise AND ~ 10^8 times.
2 Likes
plcpunk is right. Anyway, as a rule of thumb, 10^8 runs in approximately one second if we have a moderate amount of constant operations.
1 Like
I tried your code for small tricky test cases involving cycles… works good for them.
But when I changed all 1000-values to 2000-values (since n<=2000 and not <=1000), it gets a TLE.
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.
1 Like
@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.
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.
@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?