DIREL - Editorial

editorial
, , , ,
1

Problem Link: contest, practice

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

Setter’s Solution: link

Tester’s Solution: link

6 Likes
2

The links to setter and tester’s solution links back to this page itself. Please post corrected links. Thank you.

2 Likes
3

Done. Thanks for pointing this out.

4

Can someone change my code to accepted one http://www.codechef.com/viewplaintext/3787165?

5

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

6

Emm…nope, that answer is 1, since there are no cousins in this problem.

7

Gotcha, Gotta change the logic !

8

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

9

can anyone explain part 1 of the solution in detail

10

can anyone explain part 1 of the solution in detail