BubbleSortWithReversals
SRM 627 · 2014-06-16 · by fsouza
SRM 627 · 2014-06-16 · by fsouza · Dynamic Programming
Problem Statement
Problem Statement
The pseudocode shown below is an implementation of BubbleSort.
Note that the array A used in the implementation is 0-based.
That is, elements of A have indices 0 through Length(A)-1, inclusive.
int[] A and the int K.
Return the smallest possible number of swaps performed by our BubbleSort after you reverse at most K disjoint subarrays of A.
BubbleSort(A):
Repeat Length(A)-1 times:
For every i from 0 to Length(A)-2, inclusive:
If A[i] > A[i+1] then:
Swap A[i] and A[i+1]
We are going to sort the array A using the above algorithm.
However, before we do that, you are allowed to reverse at most K disjoint subarrays of A.
For example, suppose that A={10, 20, 30, 40, 50, 60, 70} and that K=1.
In this case you may, for example, reverse the subarray [2,5] - that is, the elements at (0-based) indices 2 through 5.
This would produce the array {10, 20, 60, 50, 40, 30, 70}.
We are interested in minimizing the number of swaps executed by our BubbleSort.
You are given the Constraints
- A will contain between 2 and 50 elements.
- K will be between 1 and 50.
- Each element of A will be between 1 and 1000, inclusive.
Examples
0)
{6,8,8,7,7}
1
Returns: 0
By reversing the subarray [1,4] we obtain a new array {6,7,7,8,8}. This array is already sorted and we can easily verify that our BubbleSort never swaps anything.
1)
{7,2,2,13,5,5,2}
2
Returns: 3
2)
{12,5,1,10,12,6,6,10,6,8}
2
Returns: 12
3)
{2,3,1}
2
Returns: 1
Note that the subarrays we are reversing must all be disjoint. For example, it is not allowed to reverse first the subarray [0,1] and then the subarray [0,2].
4)
{482,619,619,601,660,660,691,691,77,77,96,77}
9
Returns: 22
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BubbleSortWithReversals with a public method int getMinSwaps(vector<int> A, int K) · 136 test cases · 2 s / 256 MB per case