Can someone help me in solving this question [BOI16_swap](https://oj.uz/problem/view/BOI16_swap). ↵
>↵
You are given a sequence of n numbers $x_1, x_2, ..., x_n$. Each number↵
appears exactly once in the sequence.↵
You can modify the sequence using swaps. There are $n - 1$ consecutive turns↵
numbered $k = 2, 3, 4, ... n$. On turn you can either swap values $x_k$ and $x_{k/2}$ in the↵
sequence or do nothing.↵
What is the lexicographically minimal sequence you can obtain? ↵
↵
<spoiler>↵
I understood that the problem can be solved with dynamic programming with dp[i][j] = minimal permutation of nodes in subtree of i if node i has been set to j. But I am not understanding how is the complexity $O(nlog^2n)$ and also how to efficiently implement this solution. Also there seems to be recursive bruteforce solutions, it would be nice if someone can explain that.↵
</spoiler>↵
↵
↵
Thanks!
>↵
You are given a sequence of n numbers $x_1, x_2, ..., x_n$. Each number↵
appears exactly once in the sequence.↵
You can modify the sequence using swaps. There are $n - 1$ consecutive turns↵
numbered $k = 2, 3, 4, ... n$. On turn you can either swap values $x_k$ and $x_{k/2}$ in the↵
sequence or do nothing.↵
What is the lexicographically minimal sequence you can obtain? ↵
↵
<spoiler>↵
I understood that the problem can be solved with dynamic programming with dp[i][j] = minimal permutation of nodes in subtree of i if node i has been set to j. But I am not understanding how is the complexity $O(nlog^2n)$ and also how to efficiently implement this solution. Also there seems to be recursive bruteforce solutions, it would be nice if someone can explain that.↵
</spoiler>↵
↵
↵
Thanks!
