fndjslzvn's blog

By fndjslzvn, history, 2 months ago, In English

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

Problem: 584E - Anton and Ira

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it