TopCoder problem "SortingWithPermutation" used in TCO09 Qual 1 (Division I Level One)



Problem Statement

    A permutation p[0], p[1], ..., p[n-1] is a sequence containing each number from 0 to n-1 exactly once. The result of applying permutation p to an array a of length n is an array b of length n, where b[p[i]] = a[i] (0-based indices).

Given an array a, find a permutation which has the effect of sorting the elements of a in non-descending order, i.e., an order where each element is greater than or equal to the previous one. If there are several suitable permutations return the lexicographically smallest one.

The permutation p[0], p[1], ..., p[n-1] is considered lexicographically smaller than the permutation q[0], q[1], ..., q[n-1] if there is an index i such that p[i] < q[i] and the equation p[j] = q[j] holds for all j < i.
 

Definition

    
Class:SortingWithPermutation
Method:getPermutation
Parameters:int[]
Returns:int[]
Method signature:int[] getPermutation(int[] a)
(be sure your method is public)
    
 

Constraints

-a will contain between 1 and 50 elements, inclusive.
-Each element of a will be between 1 and 1000, inclusive.
 

Examples

0)
    
{2, 3, 1}
Returns: {1, 2, 0 }
The element that is originally at position 0 goes to position 1. The elements originally at positions 1 and 2 go to positions 2 and 0, respectively.
1)
    
{2, 1, 3, 1}
Returns: {2, 0, 3, 1 }
There are two suitable permutations - {2, 0, 3, 1} and {2, 1, 3, 0}. The first one is lexicographically smaller.
2)
    
{4, 1, 6, 1, 3, 6, 1, 4}
Returns: {4, 0, 6, 1, 3, 7, 2, 5 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13742&pm=7952

Writer:

FedorTsarev

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Sorting