@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?
Thanks! I am idiot…
@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.
2 Likes
@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.
Because dfs counts people without mutual friends as well.
dfs just assures there is a path but here we need path of length 2.
1 Like
Maybe if you read the comments and saw that I asked that question…
ohh, sorry. wrong copy-paste lol. this one should be 4. The one that should be 2 is this one:
4
0111
1011
1100
1100
is there any solution(solved) using the other method using matrix multiplication??