RRFRNDS - editorial

[dpraveen]

PROBLEM LINK:

Practice
Contest

Author: Roman Rubanenko
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Medium

PREREQUISITES:

Bitwise operations

PROBLEM:

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.

Explanation

NOTE: I have done a slight experiment in the editorial. The editorial is presented as a process of two persons asking each other questions and solving the problem with help of each other. First person’s words are written in italic while
that of second are in normal text.

Hey, I am not able to figure out anything. What is the trivial algorithm that I can have here?

As n <= 2000. O(n^3) is a trivial algorithm. For each pair of vertices u, v not having an edge between them, we will find the vertices which are
neighbour of both u and v. Let set neigh[u] denotes the neighbours of u except v. Similarly set neigh[v] denotes of v except u. Checking whether u and v are
connected is same as checking whether intersection of set neigh[u] and neigh[v] is empty or not. We can implement this intersection step in O(n) easily.

Oh, yes, I got it. Can we do it faster?

Yes, Note that for each set neigh[v], we need to maintain binary n values, i^th of them represents whether the vertex u have an edge with vertex v.

Can we make use of the fact that the values in the set are binary, can we somehow reduce the size of set and represent the information more succinctly?.

Yes, As each of the value is binary, we can store them ceil(n / 32) groups where each group is of integer data type. Note that we are here making use of bits
to encode the information of set in compressed form.

Note the size of each set will reduce by a factor of 32 (as integer data type has size 4 bytes = 32 bits).

Now you need to check whether two sets intersect or not.

I think that we can make use of bitwise operations for this.

Yes, Finding whether intersection of sets represented by two integers x and y is empty or not, can be done by checking their bitwise AND. If their bitwise
AND is non-zero, they have an intersection, otherwise not.

Few Small Points

• Note that you can also use long long instead of int too.
• Note that int has 4 bytes, but it stores both negative and positive values, so effectively for representing sets, you can not use its all bits, you
  can only use 31 bits. Normally you can solve the problem by just taking 30 bits. You can also use unsigned int and use 32 bits.

Complexity:
O((n^3) / 32), For each u, v we are having n / 32 sets. Intersection of two integers x, y can be find in constanct time because we can assume that
bitwise operations are almost constant time opertions.

So overall time complexity will n * n * n / 32 = n ³ / 32.

ANOTHER SOLUTION

Let us try to think in terms of powers of adjacency matrices. I think it can help us. What does i,j th element of powers of adjacency matrix denote?

As the entries of the adjacency matrix gives you the connections between the vertices.
If you take powers of adjacency matrix, then you are really combining the walks.
So the i,j th entry of the k^th power of the adjacency matrix tells you the number of walks of length k from vertex i to vertex j.

I understood it, but Where is the proof?

You can prove it using induction.
To form a walk of length k+1 from vertex i to j, you must first have a walk of length k from vertex i to some vertex v
and then a walk of length 1 from vertex v to vertex j.

Now relate these terms with matrix powers and you are done

How can powers help me here? I am not able to exactly formulate this.

You can note that i, j th entry of square of adjacency matrix will denote the number of walks of length 2 from vertex i to vertex j.
So you can notice that if i,j the entry is non-zero, then we can say that vertex i and j are connected with each other by another vertex w.

I can do the matrix multiplication of two square matrices of dimension n in O(n^3) time, which will get TLE, do you have some faster algorithm??

Well, there is an algorithm called Strassen_algorithm which can solve the problem in O(n ^{log ₂ 7} ).

Yes, that’s cool.

In our case, the matirces are boolean matrices, can we somehow compute their product faster?

Fortunately Yes, there is a technique called Method of Four Russians which will help us.

AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

[chandan721]

I tried solving this using two approaches.

One using Union_Find algo and another by making graph and doing dfs on each node as the constraints were small.
but both failed giving WA

Can someone who has used either of same approach tell where I went wrong??

[hatim009]

can anyone tell me where my solution is wrong .
sol : CodeChef: Practical coding for everyone

[ayushrocker92]

Hey,I used approach where i used bfs from each node and counted all those vertices with distance 2 from that node and marked them.did this for all vertices and counted total such pairs

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

I got runtime error can any1 tell me why?

[s24w]

why does dfs fail in this?

[shivam1511]

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…

[rsaha77]

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.

[scooby]

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.

[chandan721]

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

somebody please correct where I am going wrong again !!

[tamimcsedu19]

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

[pedromnasc]

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

[luckfove]

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

[minimario]

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

[gkcs]

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

[gkcs]

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

[hitesh_noty]

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

[alphaparticle]

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 .

[s24w]

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

[codeshaker]

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

[purvabaradia]

why tle ?

Ideone.com

please help…