RRFRNDS - editorial

editorial
, , ,
5

why does dfs fail in this?

1 Like
6

Were the test cases weak or something??

I mean a complexity of n^3/32 for n=2000 is over 10^8!

How does this run in 1s?
I had thought of this solution but didn’t code this because i thought 10^7 take 1s!
Someone please explain… :frowning:

5 Likes
7

Here is a clever O(N^3) solution which got AC.! I thought of something similar but didn’t code it, as i thought it would run out of time…!!

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

Obviously this solution should give TLE for a really strong test case.

9 Likes
8

Here’s my approach. Plz help me find the flaw.

  1. Find all the connected components.
  2. Store them in a vector of lists.
  3. Go through every node v in each list
  4. Sum (list_size - #of nodes connected to v - 1) for each node

For example:
1 is connected to 2 and 3
4 is connected to 5 and 6

So we have 2 connected components with size 3 and 3.

[{1,2,3}, {4,5,6}]

Step 4 will go like this.
For 1st component:

3 - 2 - 1 = 0
3 - 1 - 1 = 1
3 - 1 - 1 = 1
Total --> 2

Same for 2nd component, hence
Total suggestions will be 2 + 2 = 4

What is the problem in this approach? Please suggest.

9

I tried it using BFS also, here’s my approach

  1. Build an undirected graph of adjacency list using the matrix

  2. then performed BFS for each node

  3. In each BFS I keep track of levels of nodes, say if I start my BFS on node 1, then node 1 is on level 0 and all nodes adjacent to node 1 are on level 1 and so-on…

  4. after doing all this for each node, I just counted all the nodes which are at level 2, LEVEL 2 because as described in the problem statement above, we need to

Find out number of pairs of vertices
u, v which are connected to each other
not directly by an edge but by another
vertex w such that w is a neighbour of
both u and v.

which means the count the pair of nodes next to nodes which are adjacent to any node.

but this still failed giving another WA :frowning:

somebody please correct where I am going wrong again !!

1 Like
10

Seeing authors solution , I think wouldn’t it be easier if we just use C++ bitset ? which supports the operation . I am getting WA though here

11

What is wrong with my code: CodeChef: Practical coding for everyone ?? i expected that it will give TLE, but it gives WA.

12

seriously thought of strassen’s algorithm but dropped the idea thinking it wont work…damn !!

13

My unfinished code is given below:

sa=int(input()) 
flist=[int(input(), 2) for t in range(sa)]

total=0 for i in range(sa-1):
    for j in range(i+1, sa):
        if flist[i]&flist[j]!=0:
            total+=1

The code finds mutual friends; however, if A and B are already friends and share common friends, total is increased by 1,which is unwanted. I am at a loss at how to implement this condition efficiently; furthermore, the editorial does not explain how to do this either. What is the best way to include this restriction?

Thanks,

minimario

14

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.

www.codechef.com/viewsolution/4359945

15

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
16

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

17

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 .

18

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

19

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

20

why tle ? :frowning:

please help…

21

will this work? all pair shortest paths of cost 2

22

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
23

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

24

can we solve it using Disjoint sets concept