# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
Your solutions are really good.
Can someone pls explain D1? Shayan's solution is very elegant but I'm not able to grasp. Thnx alot in advance
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:
2**l
to the right. Wherel
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:
After each swap, if at least one non-leaf node has a misplaced child, the answer is "NO", else, it's a "YES".
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.
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!
d2 sumbission link?