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…
Complexity can be reduced to nn(n-1)/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+…+n-1=n(n-1)/2. We do this n times. This takes 6.25*10^7 operations, well within time constraints.
@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
Not really… using long and checking for only lower indices, the operations can be reduced to (n)(n)(n-1)/((64)*(2))=6.25X10^7 operations…That falls well within the time limit.
3 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
nice tutorial 
but can someone help me how to solve with strassens matrix multiplication. Can i get a code for implementing it??
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??
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
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 .
Can be solved using binary search . Complexity nnlog(n*n)
http://www.codechef.com/viewsolution/4360176
i have used distance 2 in this ques.
I am getting WA in this.
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 worst-case.
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 worst-case.
1 Like