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

E — Gardener and Tree, can someone tell me if my approach is wrong?
Автор _Spongey, история, 11 месяцев назад, По-английски

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

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

»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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)

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

      The center being the node with most neighbors? And how do you find how many operations needed?

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

    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

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

      You are not entirely correct. Check out my submission.

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

        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)

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

          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.

          → Ответить