pritishn's blog

Help needed in a Tree Question.
By pritishn, 4 years ago, In English

Original Question Statement Link : https://pastebin.com/4jH5GJqk (test cases included )

The Question basically asks ,

Given $$$K$$$ Binary Trees each rooted at it's node 1.

We can traverse normally inside a tree.

And we can also move from $$$i_{th}$$$ tree to $$$(i+1)_{th}$$$ or $$$(i-1)_{th}$$$ tree through the root nodes of both i.e go from root node of one tree to the root node next or previous tree.

We can also move from the $$$0_{th}$$$ tree to the $$$(K-1)_{th}$$$ tree and vice versa.

$$$N_i$$$ denotes the number of nodes in the $$$i_{th}$$$ tree.

Find the number of edges in the longest simple path (each node is visited once) over the entire forest of trees.

Note: if we move from $$$i_{th}$$$ tree to $$$(i+1)_{th}$$$ tree via root, we have to increase the answer by 1 as if we have an edge between both the roots,

$$$3 \leq K \leq 10^5$$$

$$$1 \leq N_i \leq 10^5$$$

$$$3 \leq \sum_{i=0}^{K-1} N_i \leq 2,000,000$$$

Time Limit : 1 Sec

I can't think of any approach to solve this. Can anyone please help me?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Just convert the forest into a tree by joining consecutive roots and compute the diameter of the tree.

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

    Aren't the binary trees joined in a cycle?

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

      well, yes. Let's say $$$h_i$$$ is the height of the $$$i^{th}$$$ tree. You must maximize this: $$$\max(h_i - i + h_j + j, h_i + i + h_j - j + K)$$$ with $$$i < j$$$. This can be done in linear time.

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

        How to do this in Linear Time???

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it 
          // ... 
int max1 = -(1<<30), max2 = -(1<<30);
for(int i = 1; i <= n; i){
	if(i > 1){
   		ans = max(ans, max1 + h[i] + i);
   		ans = max(ans, max2 + h[i] - i + K);
	}
	max1 = max(max1, h[i] - i);
	max2 = max(max2, h[i] + i);
}
          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Yes now I got it. This method looks great. Thanks for replying.

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

There are two possible ways what this longest path may look like:

  • it is the diameter of one of the trees;
  • it is a path of the form (farthest leaf of some tree)-(root of some tree)-(root of another tree)-(farthest leaf of that other tree).

To find the longest path of the first form, simply calculate each tree's diameter, this is standard.

Let's see how to find the longest path of the second tree. Store for each tree $$$i$$$ the longest path from the root to a leaf, let this value be $$$A[i]$$$. We need to find the maximum value of $$$A[i] + A[j] + d(i, j)$$$; here $$$d(i, j)$$$ is the distance between roots $$$i$$$ and $$$j$$$.

Duplicate the array $$$A$$$: we obtain an array $$$B$$$ of length $$$2n$$$, with elements $$$A[1], A[2], \ldots, A[n], A[1], A[2], \ldots, A[n]$$$. Observe that for each element $$$i$$$, there is some range to the left of $$$i$$$ so that for the $$$j$$$ in that range, we have $$$d(i, j) = i - j$$$. Store the values $$$B[j] - j$$$ in a segment tree. For each $$$i$$$, calculate the maximum value of $$$B[i] + i + B[j] - j$$$, where $$$j$$$ is taken over that range.

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

    But what if the range max query returns the same tree again? I mean for B[n+x] the answer can't be B[x] where 1<=x<=n ??

    EDIT: Nevermind, I got it. I will just modify the (j-n) th value before querying for the jth value and it won't return the same tree again.

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

      No, not like that. The range you query should only be the "half-circle" left of $$$i$$$.

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

        Yes I got it now, thanks for replying.

        → Reply