You are not logged in. Please login at www.codechef.com to post your questions!

×

RRFRNDS - editorial

46
15

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

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.

AUTHOR'S and TESTER'S SOLUTIONS:

Author's solution
Tester's solution

This question is marked "community wiki".

asked 21 Jul '14, 01:03

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 21 Jul '14, 11:14

can we solve it using Disjoint sets concept

(21 Jul '14, 01:10) apoorvneema2★
6

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

(21 Jul '14, 01:27) tacoder3★
1

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?

(21 Jul '14, 01:43) vicfred3★

Nice Solution, but could you explain the Strassen_algorithm, I got the idea of squaring the matrix but could code the matrix multiplication part.

(21 Jul '14, 01:57) saurabhsuniljain2★

Nice way to present the solution (y) @dpraveen

(21 Jul '14, 14:32) randomizer4★

is there any solution(solved) using the other method using matrix multiplication??

(21 Jul '14, 16:46) hitesh_noty3★

Can be solved using binary search . Complexity nnlog(n*n)

(21 Jul '14, 22:14) alphaparticle4★

alphaparticle: No, your solution is O(N^3 log(N)) - for each disconnected pair, you can end up checking all edges from one of them before breaking, and there can be a lot of them. It just has a really good constant and it's hard to make testcases where it runs worst-case.

(21 Jul '14, 23:52) xellos07★

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

(25 Jul '14, 19:13) vicfred3★

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

(15 Sep '14, 10:55) ashishtilokani5★
showing 5 of 10 show all

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.

link

answered 21 Jul '14, 01:45

rsaha77's gravatar image

4★rsaha77
9663815
accept rate: 17%

edited 21 Jul '14, 15:08

1

brilliantly done!

(23 Jul '14, 12:55) thespacedude2★

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

link

answered 21 Jul '14, 01:33

shivam1511's gravatar image

5★shivam1511
4382414
accept rate: 22%

2

It depends on the type of operation. In this case, we are just using bitwise AND ~ 10^8 times.

(21 Jul '14, 02:01) plcpunk5★
1

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.

(21 Jul '14, 02:05) alexpizarroj3★

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

link

answered 21 Jul '14, 11:23

gkcs's gravatar image

4★gkcs
2.6k11128
accept rate: 9%

edited 21 Jul '14, 19:04

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??

link

answered 21 Jul '14, 01:10

chandan721's gravatar image

2★chandan721
2113919
accept rate: 0%

2

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.

(21 Jul '14, 01:15) subway5★

@subway I got my mistake. thanx :)

(21 Jul '14, 01:20) chandan7212★

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

link

answered 21 Jul '14, 01:14

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

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?

link

answered 21 Jul '14, 01:20

ayushrocker92's gravatar image

3★ayushrocker92
8671217
accept rate: 0%

1

Runtime error! N is at most 1000.I don't think so!!!

(21 Jul '14, 01:55) aforapple1★

i got runtime error dont know why!.Is the solution correct?

(21 Jul '14, 02:00) ayushrocker923★

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.

(21 Jul '14, 02:20) arastogi3★

tnx got my mistake :)

(21 Jul '14, 02:46) ayushrocker923★

hey I just tried it the same way, getting WA though :(

(21 Jul '14, 02:48) chandan7212★

why does dfs fail in this?

link

answered 21 Jul '14, 01:21

s24w's gravatar image

4★s24w
456
accept rate: 0%

1

Because dfs counts people without mutual friends as well. dfs just assures there is a path but here we need path of length 2.

(21 Jul '14, 15:28) deepu_codes4★

http://www.codechef.com/viewsolution/4360176 i have used distance 2 in this ques. I am getting WA in this.

(21 Jul '14, 22:28) s24w4★

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 !!

link
This answer is marked "community wiki".

answered 21 Jul '14, 02:46

chandan721's gravatar image

2★chandan721
2113919
accept rate: 0%

Between each BFS, you might switch from one CC (connected component) of the graph to another, effectively not reaching friends that you did on previous iterations. The value of level[] for these friends will remain the same, and thus you might increase the value of ans incorrectly. Anyway, the approach is too slow and even after the correction you'll get TLE.

(21 Jul '14, 02:56) alexpizarroj3★

@alexpizarroj could you/someone else just have a look at this submission and tell why this got TLE'd ??

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

(21 Jul '14, 03:07) chandan7212★
1

In the worst case, everybody will be friends with everyone. Thus, we'll have V=n and E approximately equal to n^2. BFS's complexity is O(V+E) which gives us O(n^2). Since you're running it from every friend, you end up with O(n^3), which is way too much. I must add: author's solution is O(n^3) too, but is has a very small constant factor which results from using bitwise operations wisely.

(21 Jul '14, 03:18) alexpizarroj3★

I got it, the worst case :O

thanx again @alexpizarroj :)

(21 Jul '14, 03:25) chandan7212★

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

link

answered 06 May '15, 23:13

bholagabbar's gravatar image

4★bholagabbar
6115
accept rate: 0%

It seems my optimisations were correct!! Cuts the runtime by HALF :D Here is my submission. I'll leave it to you to understand why this works :). Common sense actually :P

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

(06 May '15, 23:21) bholagabbar4★

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/

(06 May '15, 23:34) bholagabbar4★

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.

link

answered 21 Jul '14, 02:08

scooby's gravatar image

2★scooby
11
accept rate: 0%

1

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.

(21 Jul '14, 02:23) alexpizarroj3★

@alexpizarroj just to correct, the answer to your case is 6 not 3. the relationship is mutual, if 1 is friend of 3 then 3 is also friend of 1.

(21 Jul '14, 02:35) chandan7212★

@chandan721 you're right, I will edit my answer.

(21 Jul '14, 02:46) alexpizarroj3★

@alexpizarroj : Thanks. I guess I misunderstood the problem. I was thinking that we can make suggestions to everyone in a cc who are not directly connected. Instead we need to target just the nodes which are at a distance of 2. Correct me if I am wrong.

(21 Jul '14, 14:40) scooby2★

Maybe if you read the comments and saw that I asked that question...

(21 Jul '14, 16:04) xellos07★

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

link

answered 21 Jul '14, 03:04

tamimcsedu19's gravatar image

3★tamimcsedu19
3662711
accept rate: 0%

1

have a look here...

it's a sweet simple and efficient use of bitset<>

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

(21 Jul '14, 03:10) chandan7212★

can you explain a bit more what have you done inside the loop ? I mean , you just copied the whole bitset b[i] into cur ? why did you do that?

(21 Jul '14, 03:22) tamimcsedu193★
1

@tamimcsedu actually the above one is not my solution. and there is indeed no use of 'cur'

I just got AC using the same approach, I have also put some comments along with code for more understanding.. check out..

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

(21 Jul '14, 04:08) chandan7212★

Can you explain it, please?

(21 Jul '14, 04:45) muttakyn3★

What is wrong with my code: http://www.codechef.com/viewsolution/4355232 ?? i expected that it will give TLE, but it gives WA.

link

answered 21 Jul '14, 04:07

pedromnasc's gravatar image

5★pedromnasc
111
accept rate: 0%

1

you're counting the resp in the wrong place. try this test case:

4

0011

0011

1100

1100

It should output "2", but your code outputs "4". Try changing "resp++" to "resp+=2" and breaking the third loop after the first valid "resp+=2"

(21 Jul '14, 06:46) caioaao3★

Thanks! I am idiot....

(21 Jul '14, 07:48) pedromnasc5★
2

@caioaao. Can you explain how the output is 2. According to me, it should be 4. 1 receives request from 2. 2 receives request from 1. 3 receives request from 4. 4 receives request from 3.

(21 Jul '14, 09:34) proxc3★

ohh, sorry. wrong copy-paste lol. this one should be 4. The one that should be 2 is this one: 4

0111

1011

1100

1100

(21 Jul '14, 16:05) caioaao3★

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

link

answered 21 Jul '14, 04:29

luckfove's gravatar image

4★luckfove
11
accept rate: 0%

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

link

answered 21 Jul '14, 05:51

minimario's gravatar image

2★minimario
11
accept rate: 0%

edited 21 Jul '14, 05:52

keep an adjacency matrix so you can check if A and B are friends in O(1)

(21 Jul '14, 06:49) caioaao3★

Can you provide some code for that?

Thanks!

(21 Jul '14, 07:00) minimario2★

Take a look at my code: http://www.codechef.com/viewsolution/4361047 AdjMatN is the adjacency matrix in this case. it's just a copy of the input.

(21 Jul '14, 07:05) caioaao3★

I used bitwise operators as well as the adjacency matrix; however, I am still receiving a TLE... any way to improve further?

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

(21 Jul '14, 07:47) minimario2★

well, I guess this problem has a strict time limit for python (but then again, I'm no expert in python). this is the optimized code that is equivalent to what I've done in C++: http://www.codechef.com/viewsolution/4362878

i've seen one solution that uses python and got AC, here it is: http://www.codechef.com/viewsolution/4360214

from this AC sol in python, it seems your issue is in slow I/O

(21 Jul '14, 18:17) caioaao3★

Yes; that was the problem.

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

(22 Jul '14, 04:00) minimario2★

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

(22 Jul '14, 06:19) caioaao3★
showing 5 of 7 show all

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

link

answered 21 Jul '14, 08:32

gkcs's gravatar image

4★gkcs
2.6k11128
accept rate: 9%

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

link

answered 21 Jul '14, 15:55

hitesh_noty's gravatar image

3★hitesh_noty
102459
accept rate: 0%

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

Elegant and Simple .

link

answered 21 Jul '14, 22:13

alphaparticle's gravatar image

4★alphaparticle
151411
accept rate: 25%

1

No, your solution is O(N^3 log(N)) - for each disconnected pair, you can end up checking all edges from one of them (you're not doing one binseatch, you're doing up to degree(u) binsearches) before breaking, and there can be a lot of them. It just has a really good constant and it's hard to make testcases where it runs worst-case.

(21 Jul '14, 23:54) xellos07★

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

link

answered 21 Jul '14, 22:28

s24w's gravatar image

4★s24w
456
accept rate: 0%

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

link

answered 24 Jul '14, 21:57

codeshaker's gravatar image

4★codeshaker
113
accept rate: 0%

why tle ? :( http://ideone.com/o5Q8SE please help...

link

answered 26 Jul '14, 00:10

purvabaradia's gravatar image

3★purvabaradia
1
accept rate: 0%

will this work? all pair shortest paths of cost 2

link

answered 20 Apr '15, 21:05

mysskin's gravatar image

3★mysskin
1
accept rate: 0%

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

link

answered 26 Sep '18, 14:29

hv7214's gravatar image

1★hv7214
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,658
×1,236
×15

question asked: 21 Jul '14, 01:03

question was seen: 11,483 times

last updated: 07 Mar, 22:15