shahianshu's blog

EXPTREE codechef problem not able to understand the proof , please help !!
By shahianshu, history, 6 years ago, In English

Hello,

EXPTREE Problem link

i was reading the editorial for Exptree i was not able to understand the proof mentioned by @gil_vegliach in the commments, as he mentioned that for any two vertices v1 and v2 in [1..n] in tree T1 , T2 resp., if we remove (parent[v1],v1) and (parent[v2],v2) will lead to same tree only if T1 = T2 initially but i came up with a counter example of 7 nodes 

(T1)                                           (T2)
               0                  and                           0
             /   \                                            /   \
           0      0                                          0     0
         /         \                                                \
   ( 0 )            0                                                 0
                  /   \                                             /  \
                 0     0                                            0    0
                                                                          \
                                                                          ( 0 )

v1 is the vertex marked with () in T1 and v2 is the vertex marked with () in T2 , now if i remove the edge between v1 and it's parent , and remove the edge between v2 and it's parent then i get the same tree but T1 != T2. Now i am not able to understand wheather the proof is wrong or i have understood it incorrectly

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

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

I have just had a closer look into @gil_vegliach's comment on the problem tutorial. It may be worth noting that the suggested operation of removing an edge( parent[ v ], v ) from the graph (along with the node v) does not preserve the tree structure of the remaining graph unless v is a leaf node, i.e. this operation should not be applied to each node v in the tree. On the other hand, starting with an n-node ordered tree, whose nodes are enumerated as 0, 1, 2, ..., n - 1, a new child node labeled n cannot be added to a parent (not necessarily leaf) node v, where 0 ≤ v ≤ n - 1, unless the ordering property of the resulting (n + 1)-node tree is preserved.

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

    So ,is the proof wrong and if it is can you tell me how to prove the formula p = (number of trees of node n-1)*(n-1) {mentioned in the editorial)

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

      Well, it is not clear in the comment how the n-node tree is constructed after removing edge( parent[ v ], v ). Removing non-leaf node v should imply that all edges to its children should also be removed. In this case, the resulting graph is no longer a tree as mentioned before. On the other hand, children of non-leaf node v may be inherited by parent[ v ] as orphan children after removing node v, i.e. connected directly to parent[ v ]. In this case, the resulting n-node graph is still a tree. The details in the original tutorial should be sufficient to derive the required formula.

      → Reply