PROBLEM LINK:
Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Merge Sort, Segment Tree/Fenwick Tree
PROBLEM:
Given an array A[1…N], you are allowed to swap exactly k times of adjacent numbers. Find out the minimum inversions that you can achieve.
EXPLANATION:
Basic Idea
It is worth noting that the number of swaps in bubble sort is equal to the number of inversions. And we only swap adjacent numbers in bubble sort. Therefore, we can greedily reduce the inversions in each swap. If k is less than the initial inversions I, the answer should be I – k.
To find out the number of inversion I, there are many classical solutions, such as Merge Sort, Segment Tree, and Fenwick Tree.
Corner Cases
As we have to apply exact k times, things go different when k is greater than I.
If k – I is even, we can repeatedly swap two numbers such that there will be no extra inversions after even number of swaps. Therefore, in this case, the answer should 0.
If k – I is odd, usually the answer should be 1. However, if there are duplicated numbers in the array, the answer could be 0, because we can swap these same numbers without any increases of the inversions.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.