10327 - Flip Sort
This is the standard problem of counting the number of inversions in a string of length . N length is medium; you can choose the brute-force algorithm, where you will barely get accepted, or use more optimized algorithms.
One of the possible solutions is using merge sort to count the number of inversions, which will lead to a nice 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.
- The problem does not state the width of the integers. Better be safe and stick to long long.
- You may also like to check UVa 10810
3 1 2 3 3 2 3 1
Minimum exchange operations : 0 Minimum exchange operations : 2
Introduction to Algorithms, Chapter 2 - Getting Started, Question 2-4, 'Inversions'