Algoge Judge

Editorial for Triangle Sort

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: milisav

Neka je inverzija u permutaciji svaki par indeka $(i,j)$ ~(i,j)~, za koji važi $i < j$ ~i < j~ i $A[i] > A[j]$ ~A[i] > A[j]~. Primetimo da nam je krajni cilj da za svako $i$ ~i~ važi $A[i] = i$ ~A[i] = i~. Neka je parnost permutacije broj inverzija u njoj po modulu $2$ ~2~. Primetimo da se primenom operacije ne menja parnost permutacije. Pretpostavimo da imamo bar tri indeksa za koja važi da $A[g] \neq g$ ~A[g] \neq g~. Neka je $i$ ~i~ najmanji indeks za koji važi $A[i] \neq i$ ~A[i] \neq i~. Neka je $j$ ~j~ indeks za koji važi $A[j] = i$ ~A[j] = i~ i neka je $k$ ~k~ proizvoljan indeks, različit od $i$ ~i~ i $j$ ~j~ za koji $A[k] \neq k$ ~A[k] \neq k~ (takav indeks postoji, jer za bar tri indeksa važi $A[g] \neq g$ ~A[g] \neq g~). Ukoliko je $i < k < j$ ~i < k < j~, primenimo operaciju dva puta, a ukoliko je $i < j < k$ ~i < j < k~, primenimo operaciju jednom. Posle toga će važiti $A[i] = i$ ~A[i] = i~, tj. broj indeksa za koje važi $A[g] \neq g$ ~A[g] \neq g~ će se smanjiti za bar jedan. Ovu proceduru možemo ponavljati sve dok postoje bar tri takva indeksa. Ukoliko više nije moguće ponoviti ovu proceduru, važi ili da smo sortirali niz ili da postoje tačno dva takva indeksa. Primetimo da ukoliko postoje tačno dva takva indeksa, tada je početna permutacija neparna, u suprotnom je parna. Dakle, dovoljno je proveriti parnost broja inverzija početne permutacije. Ovo se može postići koristeći _bit_ u kojem dodajemo vrednosti elemenata redom i svaki put proveravamo koliko smo većih dodali pre trenutnog u složenosti $O(N log N)$ ~O(N log N)~. Takođe je moguće rešiti zadatak u složenosti $O(N)$ ~O(N)~, simuliranjem opisane procedure.

Comments

0

grandesonnerie commented on May 10, 2020, 9:11 p.m.

How do you show the the parity of inversions remains the same when we perform the operation?

1

milisav commented on May 10, 2020, 9:31 p.m.

First, we should observe that this operation is a composition of two swaps. We will show that when two elements are swapped, parity of permutation changes. Let the two elements, which are to be swapped, be $A[i]$ ~A[i]~ and $A[j]$ ~A[j]~, $i < j$ ~i < j~. Notice that if two adjacent elements are swapped, parity changes (if $A[i] < A[i+1]$ ~A[i] < A[i+1]~, then the number of inversions increases by $1$ ~1~, otherwise it decreases by $1$ ~1~). Now note that swapping $A[i]$ ~A[i]~ and $A[j]$ ~A[j]~ is equivalent to swapping: $A[i]$ ~A[i]~ and $A[i+1]$ ~A[i+1]~, then $A[i+1]$ ~A[i+1]~ and $A[i+2]$ ~A[i+2]~, ..., then $A[j-1]$ ~A[j-1]~ and $A[j]$ ~A[j]~, then $A[j-2]$ ~A[j-2]~ and $A[j-1]$ ~A[j-1]~, ..., then $A[i+1]$ ~A[i+1]~ and $A[i]$ ~A[i]~ (imagine that we first "bring" $A[i]$ ~A[i]~ to position $j$ ~j~, and after that $A[j]$ ~A[j]~ to position $i$ ~i~). Now note that we have applied exactly $2(j-i)-1$ ~2(j-i)-1~ swaps and thus, parity changes. Since we will swap two elements twice in each operation, parity remains the same.

0

grandesonnerie commented on May 10, 2020, 9:43 p.m.

That's a great explanation! Thank you very much.

10

losmi247 commented on May 10, 2020, 8:06 p.m.

https://www.codechef.com/MAY20A/problems/TRPLSRT

😄