Problem Link: contest, practice Difficulty: Easy Prerequisites: Graphs, Shortest path problem, Adhoc 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.
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 1Let'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 2For 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(N^{2}) time. Part 3Let's do the Floyd–Warshall algorithm for the graph, that we've build during the previous parts. This part can be done in O(N^{3}) 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(N^{3} + Q). Setter's Solution: link Tester's Solution: link
This question is marked "community wiki".
asked 21 Apr '14, 00:11

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

Can someone change my code to accepted one http://www.codechef.com/viewplaintext/3787165? answered 21 Apr '14, 21:38

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

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? answered 22 Apr '14, 14:53

can anyone explain part 1 of the solution in detail answered 17 Oct '14, 02:41
