Блог пользователя fndjslzvn

Автор fndjslzvn, история, 14 месяцев назад, По-английски

Hi I have a problem understanding proof of problem 584E.

Problem: 584E - Антон и Ира

Editorial: https://codeforces.com/blog/entry/20766?locale=en

Suppose the only thing we want to calculate is the total cost. In the editorial there is an information that our task is equal to calculating the cost of transforming permutation $$$p$$$ into $$$s$$$ where $$$s$$$ is identity permutation. I don't understand why. Let's denote $$$d(a, b)$$$ as a minimal cost of transforming permutation $$$a$$$ into $$$b$$$. From what I understand in the editorial we proved that: $$$\newline$$$ $$$d(p, s) = \frac{1}{2}\sum_{i = 0}^n\mid i - C_{p_{i}}\mid$$$ where $$$C_{s_{i}} = i$$$ $$$\newline$$$ For some permutation $$$p$$$ and identity permutation $$$s$$$. $$$\newline$$$ To prove that $$$d(a, b) = \frac{1}{2}\sum_{i = 0}^n\mid i - C_{a_{i}}\mid$$$ where $$$C_{b_{i}} = i$$$ wouldn't we have to prove that $$$d(a, b) = d(\omega a, \omega b)$$$? Where $$$a$$$ and $$$b$$$ are some permutations and $$$\omega$$$ is some transposition.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится