I need help with problem D in the recent Deltix Round

Revision en1, by desperateboy12344, 2024-08-12 04:41:08

As my title stated, I really need help with understanding D (https://mirror.codeforces.com/contest/2002). (Sorry, I'm really dumb :<<<). So the statement is like this (D1): Given a permutation with some persistent swap queries and a dfs algorithm, check if the permutation after each swap can form a dfs order of some perfect binary tree. I really think that as long as the permutation starts with 1, we can always recreate a perfect binary tree from the permutation. Because like if we assign a pointer p = 0, when we traverse on a binary tree, when we enter a node u, we can just assign p = p + 1, and then assign a[u] = P[p] (P is the original permutation), hence it always exists (Did I misread the statement??). Help me guys I'm really dumb :<<<

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English desperateboy12344 2024-08-12 04:41:08 797 Initial revision (published)