Блог пользователя pritishn

Help needed in a Tree Question.
Автор pritishn, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Aren't the binary trees joined in a cycle?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        How to do this in Linear Time???

        → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится 
          // ... 
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);
}
          → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить