Hey! Is someone who can help me solve this faster than O(N^2)? The problem: initially we have an array V1 of size N with the numbers from 1 to N ordered.
Example: N = 4; V1 = {1, 2, 3, 4}.
We have a second array of N numbers, let's say V2 = {3, 2, 0, 1}. For each position 'i' from right to left, we will apply the operation "move right the element V1[i] with V2[i] positions.
We have 4 operations {3, 2, 0, 1}. Apply i = 3, so V1 will be {1, 2, 3, 4}; further we apply i = 2 (V2[2] = 0 so V1[2] stays); we apply i = 1, so we move the element '2' with 2 positions right in V1 (the array becomes {1, 3, 4, 2}. Finally we apply i = 0 so V1 becomes {3, 4, 2, 1}.
Any idea? Thank you!
Auto comment: topic has been updated by I_LOVE_ROMANIA (previous revision, new revision, compare).
As this problem is essentially asking you to delete and insert an element at particular positions, it can be done with implicit treap (or any other BBST I guess) in O(nlogn)
Maybe something like this will work:
It doesn't work..