UVa 10327

From Algorithmist
Jump to: navigation, search

10327 - Flip Sort[edit]

Summary[edit]

This is the standard problem of counting the number of inversions in a string of length n\leq 1000. N length is medium; you can choose the brute-force O(n^{2}) algorithm, where you will barely get accepted, or use more optimized algorithms.

Explanation[edit]

One of the possible solutions is using merge sort to count the number of inversions, which will lead to a nice O(n\log(n)) algorithm. While merging two sorted arrays, any move from the right array to the final merged array will represent a number of inversions if the left array is not empty. If, for example, the left array has 3 elements left, then the merge have fixed 3 inversions in one step.

The final inversion count is the sum of all inversions fixed by all the merges done by the algorithm.

Gotchas[edit]

  • The problem does not state the width of the integers. Better be safe and stick to long long.

Notes[edit]

Input[edit]

3 
1 2 3
3
2 3 1

Output[edit]

Minimum exchange operations : 0
Minimum exchange operations : 2

References[edit]

Introduction to Algorithms, Chapter 2 - Getting Started, Question 2-4, 'Inversions'