_Spongey's blog

E — Gardener and Tree, can someone tell me if my approach is wrong?
By _Spongey, history, 2 years ago, In English

Hey guys, So for this problem, my approach was to like assign every node in the tree a value, which is how long or deep is it. (IDK what it's called but basically if we had a graph: 1 --> 2, 1 --> 3, 2 --> 4. Then the height of 1 is 2, height of 2 is 1, height of 3 and 4 is zero) My code failed on test 2, 25th test. So I was wondering what am I doing wrong (If it got me TLE I was planning to dp the height and just add 1 to it) 240029463 Here's my submission, and also this submission too 240023658

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

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

How did you assign height to nodes? In the example you gave, nodes 1 and 2 appear symmetrically the same, so why do they have different heights? (Moreover, your solution is $$$O(n^2)$$$ so it will throw a TLE)

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    My approach
    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Don't know the words but I meant them setting height to them in a differnet array, and for the time complexity I was thinking of solving that by using dp, since the a node's height is the hight of it's child +1

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

      You are not entirely correct. Check out my submission.

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

        Thanks, and can you please review my code, I think I didn't implement my idea correctly (asking so later on I don't implement things wrong thinking my solution is correct)

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

          That's an $$$n^2$$$ solution, my friend. It won't get accepted anyways. I would rather recommend you solve the Tree Algorithms section of CSES.

          → Reply