Hi,
I got problem and can't solve it:
given an array consist of N integers A1,A2,A3...An
for each element i from 1 to n you should increase all elements j by (1) such that j<i and A[j]>=A[i]
example: the array is:
4 2 1 3
i=1 :
nothing before 1 so thing will happen here
i=2 :
A[i]=2 so we need to increase all element before i and bigger or equal than A[i] by 1
so the array become:
5 2 1 3
i=3 :
A[i]=1
increase all element before i and bigger ort equal than A[i] by 1
the array become:
6 3 1 3
finally when i=4 :
the array become:
7 4 1 3
so print the new array to the output
N=10^5
sorry for my English.
thanks in advance.
There is a modified O(nlgn) merge-sort algorithm which is used to calculate inversions. You can modify that easily and solve your problem ;)
Where is this algorithm?
Algorithm for number of inversions. Modify it yourself :)
1- Merge sort array A and create a copy (array B)
2- Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.
2a. accumulate the number of inversions to counter variable num_inversions.
2b. remove A[1] from array A and also from its corresponding position in array B
3- Rerun from step 2 until there are no more elements in A.
please, can you show me how to apply this algorithm on array A= 4 2 1 3
to make a better understand
thanks alot
Sure!
I applied this algorithm and got the output 7 3 1 3 instead of 7 4 1 3
actually finding inversions in not useful in this problem.
thank you anyway.
I told you so! :) Directly applying this algorithm is not useful! You should modify that!
Also you can use divide&conquer solution.
I don't think that finding inversions is useful in anyway
i am still waiting for a good idea.
Amir.bh said everything... Ok, once again.
I have very ugly solution.
to solve this problem you need data structure with operations
1) Find(X) — find object at position X
2) MoveUp(X) — move all objects from position j >= X to positions j + 1.
It's like
for (i = maxN - 1; i >= X; i--) a[i + 1] = a[i];
**upd:** for lists there must be
a[i + 1].insertAllElementsFrom(a[i]);
to implement this data structure one can use Cartesian Tree or Rope. now algorithm is straight-forward S — described structure where each cell with index from 0 to 2 * n contains an empty list of integers.