ICM2005 - Editorial (Swap Sort)

PROBLEM LINK:

Practice
Contest

Author: Mihil Gupta
Tester: Himanshu Singh
Editorialist: Mihil Gupta

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

constructive algorithm

PROBLEM:

In the problem, you were allowed to swap element x with any element which is odd index away from x (ie … i-3 i-1 i+1 i+3 … where i is the index of x). You were asked to determine whether the array can be sorted or not. If yes, then you were asked to give at most 10*n steps to sort the array.

EXPLANATION:

Array can be sorted or not ?

For determining if the array can be sorted, we will focus upon the inversion count of the array ( formed by elements except for x ). Inversion count of an array is number of pairs {i , j} such that i < j and a[i] > a[j]. If the array is already sorted then the inversion count is 0. If the array is sorted in reverse order that inversion count is maximum.

Let say, that element x (at index i) and element at index i+k are being swapped, where k is odd. Then there will be k-1 (even) number of elements between the two indexes. Let one of the indexes be j. If a[j] < a[ i+k], then after the move a[i+k] will move before a[j] leading to increase in inversion count of the initial array, and if a[j] > a[i+k] then inversion count will decrease. Hence, there will be an even number of changes to the inversion count of the array in one move, leading to the parity of the inversion count to remain the same. A similar analogy can be said for swapping elements at index i and i-k.

Thus the inversion count of the array (formed by excluding x) should be even for the array to be sortable.

Steps
We will sort the array by sequentially placing the smallest element(excluding x) one by one into their correct positions. (Note that if x is 1, then we will first place 2 in the position 1). So, we will bring the current element ( cur ) to its correct position( curi ). This can be done as follows:-
Getting x to curi. This can be done in at max 2 swaps.

if(pos[x]!=cur){
    .  if((pos[x]-cur)%2) swapp(pos[x],cur);
      else{ 
      swapp(pos[x],pos[x]-1);
      swapp(pos[x],cur);
      } }

Now there can be two cases:
a) If the distance between x and cur is odd, just swap them
b) Otherwise, first, shift x to one place towards the right. Swap x and cur. Now, we have to bring x to (curi) again. For that, we swap x with the element at (curi +3) as the position curi+1 is occupied by the cur. Now, swap x with the element at curi. Now, as the distance between x and cur is 1, just swap them.

if((pos[i]-cur)%2) swapp(pos[i],cur);
	 else{
	swapp(pos[x],pos[x]+1);
	swapp(pos[x],pos[i]);
	if(pos[i]+2>n)  break;
	swapp(pos[x],pos[i]+2);
	swapp(pos[x],pos[i]-1);
	swapp(pos[x],pos[x]+1);
	}

At last, after placing n-3 elements (excluding x), 3 elements will be left with one being x. The two elements left will already be sorted, as if not then inversion count of the current array will be 1 which will contradict our initial assumption ( inversion count parity will remain even if the array can be sorted ). Hence these two elements are also sorted.

At last, we will place x at its intended position by repetitively swapping with its adjacent element.

Time Complexity :- O(7*n)

SOLUTIONS:

Solution Link

7 Likes

Thanks for this.

Good one.

Cleverly thought, thanks!