Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

dusht0814's blog

Constructing a Tree Using It's Timestamp.
By dusht0814, history, 10 years ago, In English

I'm interested in whether we can Construct a tree if we know the Starting Time and Ending Time of all the Vertices.

For Example:

  • Number of Vertices :4
  • Starting time ST[i]:2 4 1 3
  • Ending time FT[i]:2 4 4 4

The Tree Looks Like:

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

There exists a unique tree for each VALID start and end time arrays.

A small hint for the tree construction : The direct parent of a node i shall be a node j with maximum start time, following the constraint that start[j] < start[i] and end[j] ≥ end[i].

There exists such a node j for each node i, except the root.

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

A node having s_t == f_t must be leaf node. First insert the node having s_t == 1 into the tree and set pos(a variable) equal to this node. This "pos" will tell u the the position where to append the next_node into the tree. Along with it maintain a parent array. After appending a node(say i) at pos, check if s_t[i] == f_t[i], If yes then backtrack to the parent until u find a parent having f_t greater than the s_t of node i. This will become the new pos pointer. And if "no" then pos will be set to i for next node.In this way u can insert all nodes.

→ Reply