I need a better algorithm to solve this problem.

Question

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

A permutation of the numbers 1, ..., N is a permutation 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.
A special sequence of positive integers of length N associated with each permutation N is called its inverse sequence. The i-th element of this sequence is the number of numbers j strictly less than i and to the right of i in this permutation. To rearrange
2 4 5 1 7 6 3 8
the inversion sequence is
0 1 0 2 2 1 2 0
The second element is 1, because 1 is strictly less than 2, and it looks to the right of 2 in this permutation. Similarly, the 5th element is 2, since 1 and 3 are strictly less than 5, but to the right of them 5 in this permutation, etc.
As another example, an inverse permutation sequence
8 7 6 5 4 3 2 1
is an
0 1 2 3 4 5 6 7
In this task, you will be given the inversion sequence of some permutation. Your task is to restore 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 works fine and gives the correct answer for 70% of test cases, but it crosses the time limit for the rest. Is there any other, faster algorithm to solve this issue?

Answer 1

Your algorithm has complexity O(N^2) , so for arrays of size 10^5 it takes too much time to execute. I am trying to describe a better solution:

We have N numbers. Allows you to call the return array I To solve this problem, we need to know where the K-th position is from the end of the permutation, which is still free (allows calling this function F(K) ). First, put the number N in position F(I[N] + 1) , then put the number N-1 in position F(I[N-1] + 1) , etc.

F can be calculated as follows: declare an array M size N : 1 1 1 ... 1 , determine S(X) = M[1] + M[2] + ... + M[X] . S is called the prefix sum. F(K) equal to N plus 1 minus such a lower X such that S(X) = K Each time we put the number Z in the position N + 1 - X(for K = I[Z] + 1) , we put a zero on M[X] . To find X faster than in O(N) , I can suggest using Binary Indexed Trees to calculate the prefix sums in O(logN) time and Binary Search to find an X such that S(X) is equal to some predetermined value.

The overall complexity of such an algorithm is O(N(log(N))^2) . This is an implementation in Ruby (you can play with it directly in ideon: change the input, start and check the 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(' ') 

A solution with O(N(log(N))) exists as well. It uses a kind of binary search tree : we create a BST with numbers 1, 2, 3, ... N on the vertices, then we can find the K-th number by value in O(log(N)) and also delete the vertices in O(log(N)) .

There may also be a solution with std :: set , but I can't think about it right now.

PS. I can also suggest you read some books about algo and olympiads, such as Skienna (task programming) or Cormen (introduction to algorithms)

PPS Sorry for the wrong solution that I described earlier

Answer 2

The most expensive part obviously shifts up to 100,000 elements in your result array.

If you split this array into more pieces, you can speed it up with some significant factor.

If you say 10 pieces and remember the number of elements for each fragment, you select the correct fragment for recording in accordance with the key, and then you must move the elements only for this fragment (up to 10 times less).

A new problem is how to achieve a good distribution of numbers in pieces.

---

You can also use the Linked List: http://www.cplusplus.com/reference/stl/list/

This is very effective for inserts, but sucks for random searches. But searching is just a read operation, so finding x elements can be faster (IDK) than moving x elements in an array.

Then you can use a combined approach and associate the list with multiple pointers so you can always search for the closest one.

Answer 3

Here is a really good algorithm and required coding in C ++:

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

Now the square root decomposition is performed and the insert is performed:

 #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; } 

Answer 4

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

I offer 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 ia(i) end