I need a better algorithm to solve this

Question

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?

Terbia

"You may assume that N ≤ 100000." – Nutria

If it's not required to use C++, python has sets, permutations and rearrangement (I think they're named differently). You can also make intersections unions and difference between sets in python. If you never tried python, try it, it's quite awesome for maths. – Context

Answer 1

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

Cusco

for the input 0 1 0 2 2 1 2 0, your algorithm outputs 0 4 5 2 7 1 3 8, instead of 2 4 5 1 7 6 3 8. Can you please explain why? – Terbia

So sorry, my solution was wrong... Let me try to give you another one – Cusco

Thanks! After changing some parts of your previous algorithm, it had worked but then it was also n^2 time – Terbia

(sorry to bother you again) Your algorithm works perfect but still it is just as slow as my initial algorithm, i am still getting 70% marks. – Terbia

Yeah, its beacuse your get_x function need ~N operations to perform + you call it N times. So the result is O(N^2) algo. But I suggest you to use Binary Search on Binary Indexed Tree: see in my code above - k = BinarySearch.lower_bound(ft, q[i] + 1) need ~(log(N))^2 ops every time its called. I call it N times also, so overall complexity is O(N((LogN)^2)) – Cusco

Answer 2

The most costly part is obviously shifting of up to 100 000 elements in your result array.

If you split that array into more chunks, you can speed it up by some significant factor.

If you have say 10 chunks and remember number of elements for each chunk, you select correct chunk to write to according to key and then have to shift elements only for that chunk (up to 10 times less).

The new problem is how to achieve good distribution of numbers accross the chunks.

---

Also you could use Linked list: http://www.cplusplus.com/reference/stl/list/

It is very effecient at insertions, but sucks for random seeking. But still seeking is just reading operation, so seeking x elements could be faster (IDK) than shifting x elements in array.

Then you could use combined approach and have linked list with multiple pointers, so you could always seek from the nearest one.

Piling

Its also good way. You can get with O(Nsqrt(N)) solution if you'll use chunks of size sqrt(N)... its called sqrt-decomposition. – Cusco

Answer 3

Here is a really good algorithm along with the required coding in C++:

The problem is solved using the fact that if there is 2 at place 7, then, two empty boxes are left before placing 7. So, if 0 is at 8, and 2 at 7, then reverse result array looks like: 8 _ _ 7 _ _ _ _.

Now, square root decomposition is done, and insertion is done:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n, k = 0, d, r, s, sum, temp, m, diff, check = 1;
    cin >> n;

    d = sqrt(n) + 1;
    int arr[n], result[n], indices[d], arr2[d][d], num = 1;

    for (int i = 0; i < n; i++)
        cin >> arr[i];               //The inversion sequence is accepted.

    for (int i = 0; i < d; i++)
        indices[i] = 0;              //Indices tell where to start counting from in each row.

    for (r = 0; r < d; r++)
    {
        for (s = 0; s < d; s++)
        {
            arr2[r][s] = num;       //Array is filled with 1 to n (after sqrt decomposition).
            num = num + 1;
            if (num == n+1)
            {
                check = 0; break;
            }
        }
        if (check == 0)
            break;
    }

    int l = s;
    while (l >= 0)                  //Non-Zero numbers are shifted to right and 0 placed in
    {                               //empty spaces.
        arr2[r][d-1 - k] = arr2[r][l];
        k = k + 1; l = l - 1;
    }

    k = d-1 - k + 1;
    for (int t = 0; t < k; t++)
        arr2[r][t] = 0;

    indices[r] = indices[r] + k;    //Index of the last row is shifted to first non-zero no.

    for (int i = n-1; i >= 0; i--)
    {
        sum = 0; m = 0;
        while (sum < arr[i] + 1)
        {
            sum = sum + (d - indices[m]); //Empty boxes in each row are counted.
            m = m + 1;
        }

        m = m - 1;
        sum = sum - (d - indices[m]);     //When sum = 1 + corresponding value in inversion
        diff = arr[i] + 1 - sum;          //sequence, then that particular value is made 0
        temp = indices[m] + diff - 1;     //and (that value - 1) is the index of the number
                                      //to be placed in result array.
        result[arr2[m][temp] - 1] = i+1;
        for (int w = temp - 1; w >= indices[m]; w--)
        {
            arr2[m][w + 1] = arr2[m][w];  //Then, 0 is shifted to just before non-zero number
        }                                 //in the row, and the elements are shifted right
        arr2[m][indices[m]] = 0;          //to complete the sort.
        indices[m] = indices[m] + 1;
    }                                     //This is done n times for 1 to n integers thus
                                      //giving the permutation in reverse order in result
    for (int p = n-1; p >= 0; p--)        //array.
        cout << result[p] << ' ';

    return 0;
}

Ecdysiast

Answer 4

Your algorithm is not efficient for this problem, because your complexity is O(n^2) which means 10^10 operations for some of the input cases. You have to come up with a solution that is cheaper.

I suggest you the following algorithm (indices from 1 to N):

for i=1 to N
   input a(i)
   if i==1 insert 1 into b
   else insert i into b at place i-a(i)
end

Apperceive

I suggest you to use a linked list instead of array for b – Apperceive

If linked list is used wouldn't that produce a O(n^2) algorithm? – Faught

if you count the number of insertion, it's O(n). But if you count the number of comparisons it is O(n^2). – Apperceive