dv.jakhar_'s blog

How to solve this problem, any ideas?
By dv.jakhar_, 3 years ago, In English

Statement:

There is a collection of photos to place into an empty photo album, one at a time by order of importance. Each time a photo is inserted, all subsequent photos are shifted toward right by one position.

Given the id's of the photos and the positions where each should be placed, find out the sequence of the photos in the album after all photos have been inserted.

Example:

 n = 5
 index = [0, 1, 2, 1, 2]
 identity = [0, 1, 2, 3, 4]

 Explanation:
 insert 0 at index 0
 insert 1 at index 1
 insert 2 at index 2
 insert 3 at index 1 and shift 1, 2
 insert 4 at index 2 and shift 1, 2

 output = [0, 3, 4, 1, 2]

Constraints:

1 <= n <= 2 * 10^5

0 <= index[i], identity[i] <= n

Required Tc: < O(n^2)

Update: Can someone pls help...tell me if something is missing in the problem details.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try to process the queries in the reverse order and observe what will be the final position of the element.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I tried to think like that but couldn't understand what would be the final position for each of them. Even though I've some segtree lazy approach in mind but don't know how to implement.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Use Segment tree which stores the free index currently present.

Iterate in reverse order and find the position of the current element with the help of SG

for example, let assume I have placed elements with ID 4 and 3 (from sample test case)

so segment tree after placing these two elements will look like

       3
      / \
     2    1
   /   \    \
  1     1    1
 / \   / \   |
1  0  0  1   1

where 1 indicates that this position is free.

now to find the position of the element with ID 2 which is 2 (which means we have to find 3rd free position)

to find 3rd free position we start our query from the top node, first we move to left and see if there are more than 3 free positions available in this section, if it is then we recursively move to the left,

if not (as in this case) we subtract 2 (in the case) from 3, because we have already seen 2 free spaces now we want to find (3 — 2)th free space, to find it we move our node to the right.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Although segment tree can do the work still you can use PBDS (Commonly known as ordered set) to do the same question , which is a lot easier to implement than segment tree, to find the final index of the answer you can use ordered set of pairs.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this problem can easily be solved by used treap

site
→ Reply