Cyclic Sort by Adjacent Swaps

ID: 16253

Type: Default

1000ms

256MiB

Farmer John has N cows labeled from 1 to N standing in an arbitrary order for a photograph. The cows are in a single line, and the cow in position i is c_i. Farmer John believes that the cows should line up in a cyclically sorted order. Specifically, he requires that for every i (with 1 \le i \le N-1), cow i appears somewhere to the left of cow i+1, and also cow N must appear to the left of cow 1. Thus, any cyclic rotation of the sorted order [1, 2, \dots, N] is acceptable.

For example, when N = 5 and the initial order is:

3 5 4 2 1

one acceptable order is

3 4 5 1 2

This can be achieved by swapping the adjacent cows (5 and 4) and then swapping the rightmost adjacent pair (2 and 1) — a total of 2 swaps.

Farmer John is in a hurry and is only willing to swap a single pair of adjacent cows per minute. Your task is to determine the minimum number of adjacent swaps required to transform the initial arrangement into some acceptable cyclically sorted order.

Hint: Notice that an acceptable order is uniquely determined by a choice of the leftmost cow x. If the leftmost cow is x, then the entire lineup must be [x, x+1, \dots, N, 1, 2, \dots, x-1] (with arithmetic taken modulo N where necessary). The minimum number of adjacent swaps required to transform one permutation into another is equal to the number of inversions between the two orders.

Define pos[i] as the position of cow i in the initial lineup. Consider the order corresponding to the cyclic shift starting with cow 1: [1, 2, \dots, N] which corresponds to positions [pos[1], pos[2], \dots, pos[N]]. Let

$$f(1)=\#\{(i,j)\, :\, ipos[j]\}. $$

When the cyclic order is rotated by one (i.e. the leftmost cow becomes 2 rather than 1), the inversion count updates as follows:

$$f(x+1)=f(x)+(N-1)-2\,(pos[x]-1)\quad \text{for } 1\le x<N. $$

Your goal is to choose a starting cow so that the inversion count, which equals the number of adjacent swaps needed, is minimized.

inputFormat

The first line contains a single integer N (1 $\le$ N $\le$ 100,000), representing the number of cows.

The second line contains N space‐separated integers $c_1, c_2, \dots, c_N$ representing the current order of cows.

outputFormat

Output a single integer, the minimum number of adjacent swaps required to rearrange the cows into an acceptable cyclic order.

sample

5
3 5 4 2 1

#P2995. Cyclic Sort by Adjacent Swaps

Cyclic Sort by Adjacent Swaps