RRFRNDS - editorial

editorial
, , ,
61

Yes; that was the problem.

However, this problem was quite biased against Python users IMO; did users in other languages experience the same problem?

62

nop, using slow I/O in C++ gives AC: http://www.codechef.com/viewsolution/4364866

63

brilliantly done!

1 Like
64

quality & timing of editorials have seriously improved on codechefā€¦nic work

65

is Strassen algorithm really fast enough to solve this? http://discuss.codechef.com/questions/48384/strassen-algorithm-not-fast-enough

66

why tle ? :frowning:


please helpā€¦

67

The editorials of codechef are a lot more exhaustive and easier to understand than that of codeforces.

68

will this work? all pair shortest paths of cost 2

69

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: http://www.codechef.com/viewsolution/6843913

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: http://www.codechef.com/viewsolution/6843885

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

2 Likes
70

It seems my optimisations were correct!! Cuts the runtime by HALF :smiley:
Here is my submission. Iā€™ll leave it to you to understand why this works :). Common sense actually :stuck_out_tongue:

http://www.codechef.com/viewsolution/6844004

71

Hereā€™s a similar SPOJ question I had solved. Itā€™s easier than this. I just used HashMaps there. http://www.spoj.com/problems/FACEFRND/

72

here is my solution-https://ideone.com/i2Hw32. can any tell why it is showing wrong answer!!