# UVa 10474

Jump to navigation
Jump to search

## Summary[edit]

Given N marbles which are numbered between 1..10000. The numbers may contain duplicates and not ordered.

You have to sort the marbles numbers in non decreasing order.

For each Q queries, you have to determine the position of the specified marbles in the sorted marble numbers.

## Explanation[edit]

Let

count[X]be the number of occurrence of marble X

Using the information on array count[], we can create another array (it's basically a counting sort):

marble[position], the marble number which resides in positionof the sorted marblesposition

Since we want the inverse of the *marble[position]*, we just loop 1..10000 to make an inverse array:

position[marble], the position of the marble in the sorted marbles

The complexity of having the array *marble[position]* and *position[marble]* is O(2*10000).

After having the array *position[marble]* we can answer all the queries easily in O(1).

--Felix halim 23:46, 29 Nov 2005 (EST)