Problem understanding proof problem 584E

Правка en1, от fndjslzvn, 2023-03-28 05:37:56

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 $$$S_{b_{i}} = i$$$ wouldn't we have to prove that $$$d(a, b) = d(\omega a, \omega b)$$$? Where $$$\alpha$$$ and $$$\beta$$$ are some permutations and $$$\omega$$$ is some transposition.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский fndjslzvn 2023-03-28 07:02:02 2 Tiny change: '$\nwhere $S_{b_{i}} =' -> '$\nwhere $C_{b_{i}} ='
en2 Английский fndjslzvn 2023-03-28 06:41:44 9 Tiny change: '?\nWhere $\alpha$ and $\beta$ are some' -> '?\nWhere $a$ and $b$ are some'
en1 Английский fndjslzvn 2023-03-28 05:37:56 1013 Initial revision (published)