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?
@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
Can you explain it, please?
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!
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.
I used bitwise operators as well as the adjacency matrix; however, I am still receiving a TLE… any way to improve further?