alwaysGREEEN's blog

How to solve the this DFS problem ?
By alwaysGREEEN, history, 6 years ago, In English

MILITARY PROBLEM

I am trying to solve this problem by running dfs from every node. I am getting TLE verdict. Please help me speed up my solution

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hint: Dont dfs from every node.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you run dfs from the root, you can save the sequence of accessing nodes and calculate the size of each nodes' subtree. Now if ith node's index is in and ith node's size is k, you can find your answer in your sequence from in to in+k.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did you try to understand the tutorial? If yes, please, tell what part you didn't understand(even if you didn't understand anything).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I will describe my approach which i believe is a bit easier than the one described in editorial.
First of all we run dfs from an arbitrary node which we set as the root (eg. node 1) and push each node processed from dfs into a set. We can see that this will generate the set from the sample. Now by definition when we have a query {u, k} we are interested in the k-th element in set counting from the index of u in the set. We are now left with calculating whether the answer is -1. We can do this slightly different than the approach described in editorial. For each node we count the number of nodes in it's subtree and now we node that if #of nodes in u's subtree < k then answer is -1.

My code: 40438205

→ Reply