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.
- A is father of B
- A is mother of B
- A is brother of B
- A is sister of B
- A is son of B
- 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(N^{2}) 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(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