TopCoder problem "PartSorting" used in SRM 307 (Division I Level One , Division II Level Two)



Problem Statement

    You are given a int[] data. All elements in data are distinct. Only consecutive pairs of elements in data can be swapped. You are allowed to perform at most nSwaps swaps. Return the lexicographically maximal possible result.
 

Definition

    
Class:PartSorting
Method:process
Parameters:int[], int
Returns:int[]
Method signature:int[] process(int[] data, int nSwaps)
(be sure your method is public)
    
 

Notes

-Given two int[]s a and b of equal length, a is lexicographically greater than b if an index i (0 <= i < n) exists such that a[0] = b[0], a[1] = b[1], ..., a[i - 1] = b[i - 1] and a[i] > b[i], where n is the size of a.
 

Constraints

-data will contain between 1 and 50 elements, inclusive.
-Each element in data will be between 1 and 1000000, inclusive.
-All elements in data will be distinct.
-nSwaps will be between 0 and 1000000, inclusive.
 

Examples

0)
    
{10, 20, 30, 40, 50, 60, 70}
1
Returns: {20, 10, 30, 40, 50, 60, 70 }
Swap the first two elements.
1)
    
{3, 5, 1, 2, 4}
2
Returns: {5, 3, 2, 1, 4 }
First, swap the third and fourth elements, and then, swap the first and second elements.
2)
    
{19, 20, 17, 18, 15, 16, 13, 14, 11, 12}
5
Returns: {20, 19, 18, 17, 16, 15, 14, 13, 12, 11 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6447

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9987&pm=6447

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Greedy, Sorting