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

×

DIREL - Editorial

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

This question is marked "community wiki".

asked 21 Apr '14, 00:11

kostya_by's gravatar image

6★kostya_by ♦♦
166143235
accept rate: 0%

edited 21 Apr '14, 01:14


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

link

answered 21 Apr '14, 00:47

kcahdog's gravatar image

3★kcahdog
10.0k2854129
accept rate: 14%

Done. Thanks for pointing this out.

(21 Apr '14, 01:14) kostya_by ♦♦6★

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

link

answered 21 Apr '14, 21:38

nurbas96's gravatar image

3★nurbas96
1
accept rate: 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

link

answered 21 Apr '14, 23:26

nehemiahjacob's gravatar image

2★nehemiahjacob
11
accept rate: 0%

edited 21 Apr '14, 23:47

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

(22 Apr '14, 00:27) kostya_by ♦♦6★

Gotcha, Gotta change the logic !

(22 Apr '14, 01:46) nehemiahjacob2★

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

link

answered 22 Apr '14, 14:53

nehemiahjacob's gravatar image

2★nehemiahjacob
11
accept rate: 0%

can anyone explain part 1 of the solution in detail

(17 Oct '14, 02:40) nil962★

can anyone explain part 1 of the solution in detail

link

answered 17 Oct '14, 02:41

nil96's gravatar image

2★nil96
18071845
accept rate: 5%

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