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

Автор Shayan, история, 3 месяца назад, По-английски
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

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

Your solutions are really good.

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

Can someone pls explain D1? Shayan's solution is very elegant but I'm not able to grasp. Thnx alot in advance

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

    Not exactly the same explanation in the video (as I didn't get it fully myself), but here is my understanding (might be wrong):

    Idea: Keep track of which nodes of the tree have correctly placed children (think bool[n]). If in a permutation, all nodes have their children in the correct positions, then it is a valid DFS order.

    Note: We can ignore leaf nodes as they don't have children => "Always valid".

    We start by checking which nodes have correctly placed children. I.e. For each non-leaf/parent node, we check that:

    • It is the parent of the node to the right of it.
    • AND It is the parent of the node 2**l to the right. Where l is the level of the parent (0 being the bottom/leaf level).

    After each swap, we don't need to re-check the whole tree. We can just check, for each of the two swapped nodes (w/ some exceptions for root and leaf nodes) if:

    • Its two children are correctly placed (see method above).
    • AND Its parent has correctly placed children.

    After each swap, if at least one non-leaf node has a misplaced child, the answer is "NO", else, it's a "YES".

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

      Ohh nice! Thanks for the explanation.

      Also, I now understand what Shayan meant in the video. A text reference helps a lot. Thnx for taking out the time.

»
3 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Why so many downvotes? He's doing great work. Taking out time, helping us understand & follow his thinking process & consistent streams for all rounds, with recent weekly topic streams as well. Such good contents & that too for free.

Upvoting and appreciation is the best that we can do! Pls don't downvote guys!

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

d2 sumbission link?