I need a better algorithm to solve this

Here is the question (link: http://opc.iarcs.org.in/index.php/problems/FINDPERM) :

A permutation of the numbers 1, ..., N is a rearrangment of these numbers. For example
2 4 5 1 7 6 3 8
is a permutation of 1,2, ..., 8. Of course,
1 2 3 4 5 6 7 8
is also a permutation of 1, 2, ..., 8.
Associated with each permutation of N is a special sequence of positive integers of length N called its inversion sequence. The ith element of this sequence is the number of numbers j that are strictly less than i and appear to the right of i in this permutation. For the permutation
2 4 5 1 7 6 3 8
the inversion sequence is
0 1 0 2 2 1 2 0
The 2nd element is 1 because 1 is strictly less than 2 and it appears to the right of 2 in this permutation. Similarly, the 5th element is 2 since 1 and 3 are strictly less than 5 but appear to the right of 5 in this permutation and so on.
As another example, the inversion sequence of the permutation
8 7 6 5 4 3 2 1
is
0 1 2 3 4 5 6 7
In this problem, you will be given the inversion sequence of some permutation. Your task is to reconstruct the permutation from this sequence.

I came up with this code:

#include <iostream>

using namespace std;

void insert(int key, int *array, int value , int size){
    int i = 0;
    for(i = 0; i < key; i++){
        int j = size - i;
        array[ j ] = array[ j - 1 ];
    }
    array[ size - i ] = value;
}

int main(){

    int n;
    cin >> n;
    int array[ n ];
    int key;

    for( int i = 0; i < n; i++ ){
        cin >> key;
        insert( key, array, i + 1, i);
    }

    for(int i = 0;i < n;i ++){
        cout << array[i] << " ";
    }

return 0;
}

It is working fine and giving correct answer for 70% of the test cases but crosses the time limit for the remaining. Is there any other, faster algorithm to solve this question?

Solution

Your algo has complexity O(N^2) operations so for arrays of size 10^5 it need too much time to perform. I try to describe better solution:

We have N numbers. Lets call inverse array I. Solving this problem we need to know where is K-th position from the end of permutation which is still free (lets call this function F(K)). First, we put number N to position F(I[N] + 1), then put number N-1 to position F(I[N-1] + 1) and so on.

F can be calculated as follows: declare array M of size N: 1 1 1 ... 1, define S(X) = M[1] + M[2] + ... + M[X]. S is known as prefix sum. F(K) equal to N plus 1 minus such lower X that S(X) = K. Every time we place number Z to position N + 1 - X(for K = I[Z] + 1) we put zero to M[X]. To find X faster then in O(N) time I can suggest to use Binary Indexed Trees to calculate prefix sums in O(logN) time, and Binary Search to find such X that S(X) equal to some predefined value.

The total complexity of such algo is O(N(log(N))^2). This is the implementation in Ruby (you can play with it right in ideone: change input, run and check output):

# O(n(log(n))^2) solution for http://opc.iarcs.org.in/index.php/problems/FINDPERM

# Binary Indexed Tree (by Peter Fenwick)
# http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
class FenwickTree

  # Initialize array 1..n with 0s
  def initialize(n)
    @n = n
    @m = [0] * (n + 1)
  end

  # Add value v to cell i
  def add(i, v)
    while i <= @n
      @m[i] += v
      i += i & -i
    end
  end

  # Get sum on 1..i
  def sum(i)
    s = 0
    while i > 0
      s += @m[i]
      i -= i & -i
    end
    s
  end

  # Array size
  def n
    return @n
  end

end

# Classical binary search
# http://en.wikipedia.org/wiki/Binary_search_algorithm
class BinarySearch

  # Find lower index i such that ft.sum(i) == s
  def self.lower_bound(ft, s)
    l, r = 1, ft.n
    while l < r
      c = (l + r) / 2
      if ft.sum(c) < s
        l = c + 1
      else
        r = c
      end
    end
    l
  end

end

# Read input data
n = gets.to_i
q = gets.split.map &:to_i

# Initialize Fenwick tree
ft = FenwickTree.new(n)
1.upto(n) do |i|
  ft.add i, 1
end

# Find the answer
ans = [0] * n
(n - 1).downto(0) do |i|
  k = BinarySearch.lower_bound(ft, q[i] + 1)
  ans[n - k] = i + 1
  ft.add k, -1
end
puts ans.join(' ')

Solution with O(N(log(N))) time exists also. It uses some kind of Binary Search Tree: we create BST with numbers 1, 2, 3, ... N on verteces, then we can find K-th number by value in O(log(N)) and delete verteces in O(log(N)) time also.

Also solution with std::set may exists but I can't think one right now.

PS. I can also suggest you to read some books on algo and olimpyads like Skienna (Programming Challenges) or Cormen (Introduction to Algorithms)

PPS.So sorry for wrong solution I described before