PROBLEM LINK:
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 3 / 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 2 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.
