I recently had to solve this problem for a test, but was not able to find an efficient solution for the same.
Is it possible to make 'n' insertions to a linked list efficiently when we are given the positions of all insertion, and the element which has to be inserted.
Eg: position = [0,1,2,1,2] , elements = [5,6,7,8,9], list = []
So basically the operations we would be doing are
- add 5 at 0th index in list =>
list = [5] - add 6 at 1st index in list =>
list = [5, 6] - add 7 at 2nd index in list =>
list = [5, 6, 7] - add 8 at 1st index in list =>
list = [5, 8, 6, 7] - add 9 at 2nd index in list =>
list = [5, 8, 9, 6, 7]
So the final list would be [5, 8, 9, 6, 7]
Does anyone know an efficient solution for the same? (better than O(n^2)) In the original problem the elements to be inserted are between 0 to n-1
Auto comment: topic has been updated by SevenDeadlySins (previous revision, new revision, compare).
treap.
Can you plz elaborate on the solution? I was thinking on these lines but couldn't reach a concrete solution.
Segment tree is enough, try to add elements from the last to the first one.
Can you plz elaborate on the solution? How are using segment tree? and for what?
Huh, I messed something up, but I’ve come up with another solution. Let’s find the rightmost 0, we know it’d be the 0-th element. Also all elements before him, should move „one position to the right” so we add 1 to the elements, which were before this one. We can see that we can go on with this algorithm, so in every step: we pick rightmost minimum, add 1 to all elements before this one (on prefix) and then change this element to inf. We can handle this operations with seg tree.
That's working. Thanks for your help.
let's turn these two arrays into a list of queries.
the i-th query will be represented as [position, element, index] where index is i
this holds true for any two queries:
- the one with the smaller position value comes first in output list
- but when two positions are equal, a query processed later will come first
Solution:
sort this list of queries by position in ascending order or by index in descending order if positions are equal
append to linked list in order of sorted query list.
This method doesn't work. Please observe the position of element at which it was inserted.
By your method, solution would be
I found a better approach for this,
Method:: Make an ordered_set_pair<long double, int> named set. insert {0,-1} and {1,-1} in it. traverse elements and insert {val,ind} in it. where ind is index of that element i.e. 0,1,2,3,..,n-1 val is (set.find_by_order(position[i])->first + set.find_by_order(position[i]+1)->first)/2
after inserting all the elements in set. traverse set and make answer array. answer[i] = elements[set.find_by_order(i+1)->second]
Logic:: Here, we have set two boundries 0 and 1. If we want to insert elements at some position, we will find it's future neighbours and assign average of them to it. In this case for the first element we will assign 0.5. Similary when we assign values in between, at the end we have our array handy in the set by order.
If n is around 1e5, this immediately fails since in the worse case, we might have to compute 1/2^n and long double's precision won't cut it.