RRFRNDS - editorial

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.

www.codechef.com/viewsolution/4359945

3 Likes

nice tutorial :slight_smile: but can someone help me how to solve with strassens matrix multiplication. Can i get a code for implementing it??

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 : CodeChef: Practical coding for everyone

Elegant and Simple .

http://www.codechef.com/viewsolution/4360176
please I need why this codes fails.

quality & timing of editorials have seriously improved on codechef…nic work

why tle ? :frowning:

please help…

will this work? all pair shortest paths of cost 2

Here are solutions both in JAVA and C++.

Both of them use BitSet concept. I’ll try and write this in terms for even a layman to understand. If you’re a beginner, i’m assuming you know what the ‘&’ bitwise operator returns for 2 binary values. If you don’t then just google it. It’s pretty easy

C++:

  1. build up the bitset. ‘bitset gr[no. of vertices]’
  2. now run a loop for each vertex. Check for the vertices for this vertex which do not share a common edge (bit will not be set e.i 1 here)
  3. simply put if((i!=j)&&((gr[i]&gr[j]).any()>0)) then ans++; [.any() method checks if the number gr[i]&gr[j] has any bit set as 1. This would obviously physically mean that they share one or more than 1 common edge]
  4. Voila!. Once you’ve interated through all loops, you have your answer.

My C++ submission: CodeChef: Practical coding for everyone

JAVA:

Same concept. Its gets much easier here.JAVA has an awesome ‘Bitset.intersects(BitSet)’ method. Intersect means that they have atleast one common bit set.

1.Create an ArrayList of Bitsets and build the graph up.

2.Now same. run a loop for each vertex to check for non adjacent vertices. After that, simply check when (i!=j && !gr.get(i).get(j)) → if(gr.get(i).intersects(gr.get(j))), ans++;

CAUTION: the second .get(j) is a bitset method. Not the arrayList one. It checks if the bit is set at position j

DONE!

My JAVA submission: CodeChef: Practical coding for everyone

Meanwhile, i’m picking up some of my old WA and TLE submission and try and make a few optimisations here :smiley:

2 Likes

here is my solution-i2Hw32 - Online Java Compiler & Debugging Tool - Ideone.com. can any tell why it is showing wrong answer!!

can we solve it using Disjoint sets concept

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

@subway I got my mistake. thanx :slight_smile:

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.