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

×

KNODES - Editorial

6
2

PROBLEM LINK:

Practice
Contest

Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey

DIFFICULTY:

Medium

PREREQUISITES:

DFS

PROBLEM:

You are given a tree. You need to process $Q$ queries. Each query gives you $K$ nodes and you need to print "Yes" if there is a path connecting them, and "No" otherwise.

Quick Explanation:

We will try building a path to solve this problem. A path will have $2$ end points and we will first try to find out these two end points (say $D$ and $RD$) and then try to check if all the nodes lie either on the path from $D$ to the root or from $RD$ to root.

Now, if the above conditions are satisfied, we need to check whether they still form a pair or not. Solution contains a detailed explanation of the approach.

Solution:

Fix any node as root of the tree. Then do a depth-first traversal and store 3 things for each node:

  1. Depth of the node : It is the distance of the node from the root.

  2. Start time of the dfs : It is the time when the dfs started on the node.

  3. End time of the dfs : It is the time when the dfs ended on the node.

You can increase time by $1$ when moving to an unvisited node.

Now for all the given $K$ nodes, find the deepest node and the node closest to root.

Let the deepest node be $D$ and let the node closest to root be $S$.

We will now partition the set of $K$ nodes into two disjoint sets $\mathbf{A}$ and $\mathbf{B}$.

Set $\mathbf{A}$ will contain nodes which are on the path from root to $D$. Set $B$ will contain the remaining nodes.

How to make set $\mathbf{A}$?

If the start time of node $X$ is before the start time of node $D$ and the end time of node $X$ is after the end time of node $D$ then node $X$ belongs to set $\mathbf{A}$. [Using properties of DFS]

If set $\mathbf{B}$ was a null set, then our answer is "Yes".

Find the deepest node in the set $\mathbf{B}$, let us name it as $RD$. [Deepest node in the remaining nodes/set $\mathbf{B}$]

Now again follow the same procedure to partition the set $\mathbf{B}$ into $\mathbf{C}$ and $\mathbf{E}$ where set $\mathbf{C}$ contains nodes from set $\mathbf{B}$ which are on the path from $RD$ to root of the tree.

If set $\mathbf{E}$ is not empty, then our answer is "No". ( Reasons ? : I hope the readers to use pen and paper to draw a diagram and understand how things are moving, from there it will be trivial to find the reason)

Now, Find the LCA of $D$ and $RD$. Let us call this node as $L$.

$L$ must lie between $S$ (smallest depth node in $K$ nodes) and root of the tree for a valid path to exists.

Reason:

If $S$ lies in between root and $L$, then there does not exist any path.

$L$ must be repeated twice in the journey from $D$ to $RD$. Hence not a path.

Time complexity of this algorithm is $\mathcal{O}(N)$ (for dfs part per test case) + $\mathcal{O}(K+log(N))$ (per query).

AUTHOR'S, TESTER'S SOLUTIONS:

setter's solution
tester's solution

This question is marked "community wiki".

asked 30 Jun '15, 16:03

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136170
accept rate: 20%

edited 20 Jul '15, 00:12

admin's gravatar image

0★admin ♦♦
19.7k350498541

3

can this problem also be solved using LCA?

(20 Jul '15, 00:20) chandan7212★

Answer to the question by @fauzdar65:
Try running it on this test:
6
1 2
2 3
3 4
3 5
5 6
1
5
1 2 3 4 6

The answer should be "No".

Here's another test:
6
1 2
1 3
2 4
3 5
5 6
1
3
2 4 6

The answer should be "Yes".

link

answered 20 Jul '15, 01:34

geeky's gravatar image

6★geeky
211
accept rate: 0%

edited 20 Jul '15, 01:41

thanks.. it was failing for these cases when the current path doesn't include root.. however with some modification got AC now ..

(20 Jul '15, 02:07) fauzdar653★

Alternative solution:

Find Leftmost deepest node (say L) and rightmost deepest node (say R). This can be easily done in O(K) :

  1. R is the node having maximum value of DFS StartTime amongst all the K nodes.
  2. Finding L is not exactly same as finding minimum because there is an edge case of two nodes lying on the same path to the root which needs to be handled differently. Approach:
    1. Initialize L = Input[0].
    2. For-each 'node' in Input:
    3. IF L and 'node' lie on the same path to the root, then make L='node' iff 'node' lies below L.
    4. Otherwise make L='node' iff DFS StartTime of 'node' is less than DFS StartTime of L.

Now any node should be lie in the path of L -> LCA(L,R) OR R->LCA(L,R).

Code: https://www.codechef.com/viewsolution/7511572

link

answered 20 Jul '15, 04:05

not_a_coder_'s gravatar image

0★not_a_coder_
211
accept rate: 0%

edited 20 Jul '15, 06:38

how did you get the values of 'L' and 'R'?

(20 Jul '15, 04:47) ironmandhruv4★

Updated the description.

(20 Jul '15, 06:37) not_a_coder_0★

Here is another approach (source): pick first and last vertex of path (start and finish); now for every vertex it lies on the path if and only if dist(v,start)+dist(v,finish)=dist(start,finish). You may find every distance in log(N) time using LCA.

link

answered 25 Jul '15, 02:57

lebron's gravatar image

7★lebron
3.3k317
accept rate: 24%

can anyone point out flaw in this: 1)sort the k nodes by their depth. Keep track of left and right end of the final path(initially,first 2 vertices are the left and right ends).

2)If answer is Yes,current node will always be the child of left end or right end, since nodes are sorted by depth.

3)So i check if current node has left or right end as ancestor. If no, ans is no,else update left or right end then check next node.

link

answered 20 Jul '15, 01:00

fauzdar65's gravatar image

3★fauzdar65
29114
accept rate: 21%

"first 2 vertices are the left and right ends" is wrong. It could turn out that the second node is the parent of the first node.

(20 Jul '15, 01:04) gdisastery14★

no they are sorted by depth so second can't be the parent of first

(20 Jul '15, 01:10) fauzdar653★

Given the set of K nodes, is there some way to find the two nodes with maximum distance between them?

link

answered 20 Jul '15, 00:31

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%

It's solvable with central decomposition tree with O(K log N) complexity.

(20 Jul '15, 00:37) gdisastery14★

yes. i guess it can be solved using LCA. order will be Klog(n) and as K<=10^6, so it should pass time limit.

make a dfs on the tree and store depth of nodes ( top has 1 depth) . now, for a Query, from K nodes, take the node which has least depth , if more than 1 nodes then answer is no. now, start moving nodes with highest depth towards the lowest depth.

if both sets empty: add node to A set.

else if A non-empty: then check of that node if it belongs to set A or not, to check it belongs or not, that just compare the bottom node of A. LCA( bottomnodeofA, node) == node, then node belongs to A set and add to set A. else not.

if node has not been added yet: check if B is empty, if yes , just add it to set B, else check the same way as we did for SET A.

if still has not added : then it means there does not exist any such path.

Order will be K*log(N) as we are checking LCA for each of K node.

link

answered 20 Jul '15, 00:33

t1g0f8b8sgresu's gravatar image

2★t1g0f8b8sgresu
111
accept rate: 0%

edited 20 Jul '15, 00:36

K*log(N) solution is not passing.

(20 Jul '15, 00:42) aj954★

may be with little optimization, it wil pass

(20 Jul '15, 01:09) t1g0f8b8sgresu2★

@admin if we do dfs and keep track of the connecting components like all nodes vs their group no(connected). then for each query we just need to go that positions and check whether all contain the same group no or not.

link

answered 20 Jul '15, 05:33

Shiva_c's gravatar image

1★Shiva_c
1
accept rate: 0%

Can't figure out why the sunmission is going wrong . Tried amost every test case . Plz help ....! Submission link

link

answered 24 Jul '15, 03:47

ayushgupta123's gravatar image

3★ayushgupta123
11
accept rate: 0%

Can anbody give me a test case where my code is failing

link to code: https://www.codechef.com/viewsolution/20359765

link

answered 28 Sep '18, 16:55

ayushpatidar's gravatar image

4★ayushpatidar
11
accept rate: 0%

Can anbody give me a test case where my code is failing

link to code: https://www.codechef.com/viewsolution/20359765

link

answered 28 Sep '18, 16:56

ayushpatidar's gravatar image

4★ayushpatidar
11
accept rate: 0%

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,482
×2,557
×496
×48
×15

question asked: 30 Jun '15, 16:03

question was seen: 6,300 times

last updated: 28 Sep '18, 16:56