Shayan's blog

By Shayan, history, 3 months ago, In English
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solutions are really good.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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 months ago, # |
  Vote: I like it +1 Vote: I do not like it

d2 sumbission link?