Help needed in BOI 2016 -— Swaps.
Difference between en1 and en2, changed 104 character(s)
Can someone help me in solving this question [BOI16_swap](https://oj.uz/problem/view/BOI16_swap). ↵
↵
<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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English toxic_hack 2020-03-31 11:11:28 16 Tiny change: 'n obtain? \n\n<spoil' -> 'n obtain? $n \leq 2 * 1e5$\n\n<spoil'
en3 English toxic_hack 2020-03-31 10:40:42 379 Tiny change: 'There are n - 1 consecuti' -> 'There are $n - 1$ consecuti'
en2 English toxic_hack 2020-03-30 21:18:11 104
en1 English toxic_hack 2020-03-30 19:14:51 440 Initial revision (published)