×

DIREL - Editorial

Difficulty: Easy

Pre-requisites: Graphs, Shortest path problem, Ad-hoc

Problem:

We are given N persons and R binary relations(like "Vanessa is sister of Jack"). Our task is to answer Q questions of the following type: for two persons X and Y we should determine how many words it takes to describe the relationships of X and Y(i.e. "Tom is father of brother of father of Mike" takes three words(father, brother, father)). There can be more than one way to do it, in that case we are looking for the shortest description.

Explanation:

Firstly, let's have a close look at the list of all possible binary relations that are allowed in this problem.

1. A is father of B
2. A is mother of B
3. A is brother of B
4. A is sister of B
5. A is son of B
6. A is daughter of B

The first and the second type of binary relations declares, that person A is a parent to person B.

The third and the fourth type of binary relations declares, that persons A and B are in sibling relationships.

The fifth and the sixth type of binary relations declares, that person B is a parent to person A.

OK, now let's assign a vertex of some directed graph to each person. Each binary relation is an edge in this graph.

Let's divide our algorithm into three parts.

Part 1

Let's add the edges between the vertices, that are siblings. If there are two vertices in one connected component, that don't share a common edge, let's add an edge between them too( because if A is a sibling of B, B is a sibling of C, then A is a sibling of C). If two vertices have a common parent, then they are siblings as well(generally, they are not necessarily, but according to the statement, in our case they are), let's also add an edge between them.

This part can be done in O(N + R) time.

Part 2

For each connected component in the graph let's merge the lists of their parents. After that, let's add the edge between every parent from the merged list and every vertex from the current component.

This part can be done in O(N2) time.

Part 3

Let's do the Floyd–Warshall algorithm for the graph, that we've build during the previous parts.

This part can be done in O(N3) time.

Well, that's all. Now, for each query we can answer in O(1) time since we know all the distances in the graph.

The total complexity is O(N3 + Q).

This question is marked "community wiki".

166143235
accept rate: 0%

 2 The links to setter and tester's solution links back to this page itself. Please post corrected links. Thank you. answered 21 Apr '14, 00:47 3★kcahdog 10.0k●28●54●129 accept rate: 14% Done. Thanks for pointing this out. (21 Apr '14, 01:14)
 0 Can someone change my code to accepted one http://www.codechef.com/viewplaintext/3787165? answered 21 Apr '14, 21:38 3★nurbas96 1 accept rate: 0%
 0 Hello, I tested for the problem my locally and it works fine. But I am getting runtime error while submitting. Seems I am not doing the input reading part correctly. Can somebody guide me how to read input string for Python3? http://www.codechef.com/viewsolution/3787326 Note: The given example output has an error, Because query 5 (john anne) should return 3 since John -> Kel ->Cloe -> Anne answered 21 Apr '14, 23:26 1●1 accept rate: 0% Emm...nope, that answer is 1, since there are no cousins in this problem. (22 Apr '14, 00:27) Gotcha, Gotta change the logic ! (22 Apr '14, 01:46)
 0 I have changed the logic & now I get run time error, Is there any way to get the test case against which my code is getting run time error? Where can I get extra test cases? http://www.codechef.com/viewsolution/3787944 answered 22 Apr '14, 14:53 1●1 accept rate: 0% can anyone explain part 1 of the solution in detail (17 Oct '14, 02:40) nil962★
 0 can anyone explain part 1 of the solution in detail answered 17 Oct '14, 02:41 2★nil96 180●7●18●45 accept rate: 5%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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
×3,820
×1,236
×968
×5

question asked: 21 Apr '14, 00:11

question was seen: 3,086 times

last updated: 17 Oct '14, 02:41