Problem understanding proof problem 584E

Revision en3, by fndjslzvn, 2023-03-28 07:02:02

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English fndjslzvn 2023-03-28 07:02:02 2 Tiny change: '$\nwhere $S_{b_{i}} =' -> '$\nwhere $C_{b_{i}} ='
en2 English fndjslzvn 2023-03-28 06:41:44 9 Tiny change: '?\nWhere $\alpha$ and $\beta$ are some' -> '?\nWhere $a$ and $b$ are some'
en1 English fndjslzvn 2023-03-28 05:37:56 1013 Initial revision (published)