RRFRNDS - editorial

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 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 :slight_smile:

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. :slight_smile:

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

46 Likes

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 :frowning:

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

1 Like

can we solve it using Disjoint sets concept

can anyone tell me where my solution is wrong .
sol : http://www.codechef.com/viewsolution/4359430

1 Like

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:

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?

1 Like

why does dfs fail in this?

1 Like

I have to say i love the idea of 2 persons interacting with each in the editorial. Amazing stuff!!

6 Likes

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

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

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

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

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.

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.

Consider the following example with 5 friends: 1->2, 1->3, 2->4, 3->5. The expected answer is 6, while your algorithm gives 12. a) 2 and 3 are not friends, but they have friend 1 in common. b) 4 and 1 are not friends, but they have friend 2 in common. c) 5 and 1 are not friends, but they have friend 3 in common. The issue with your approach is that you only get the sum of the number of indirectly connected friends in the CC (for every friend), and that doesn’t help us at all to compute the desired answer.

1 Like
//