UVa 10810

From Algorithmist
Jump to navigation Jump to 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 , the pair is an inversion of if and . You have to find the inversions count of given sequences of length .

is huge; a brute-force 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, ( , , ), number of swaps will equal:

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

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