UVa 10810

From Algorithmist
Jump to: navigation, search

10810 - Ultra-QuickSort[edit]

Summary[edit]

To find number of adjacent swaps necessary to sort a given sequence of integers.

Explanation[edit]

In a sequence A, the pair (i,j) is an inversion of A if i<j and A_{i}>A_{j}. You have to find the inversions count of given sequences of length n<500000.

n is huge; a brute-force O(n^{2}) bubble sort algorithm won't pass. Similar to UVa 10327, exploit the merge sort algorithm to calculate inversions count.

Note[edit]

In the worst case of a completely unsorted list, (i,j <n, i<j, A_{i}\geq A_{j}), number of swaps will equal:

(n-1)+(n-2)+(n-3)+\ldots +(n-(n-1))={\frac  {n(n-1)}{2}}

where n is the string length. Remembering that we have a huge n<5000000, maximum number of swaps will equal:

{\frac  {(5000000-1)(5000000-2)}{2}}=12499992500001

which far exceeds the capacity of a 32-bit integer. Thus, use 64-bit integers for the inversions count.

Use long long to count swaps.

Input[edit]

5
9
1
0
5
4
3
1
2
3
5
5
2
3
4
1
0

Output[edit]

6
0
7