### Shayan's blog

By Shayan, history, 4 weeks ago,

Video

Video

Video

Video

### 2002E — Cosmic Rays

Video
• +6

 » 4 weeks ago, # |   0 Your solutions are really good.
 » 4 weeks ago, # |   0 Can someone pls explain D1? Shayan's solution is very elegant but I'm not able to grasp. Thnx alot in advance
•  » » 4 weeks ago, # ^ |   +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".
•  » » » 4 weeks ago, # ^ |   +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.
 » 4 weeks ago, # |   +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!
 » 4 weeks ago, # |   +1 d2 sumbission link?