444iq's blog

By 444iq, history, 5 years ago, In English

You are given a permutation of N numbers from 1 to N in an array

You want to sort the array using this operation

  1. Send the front-most element X places back in the array;
  2. Add x to the total cost.

N<=10^5

Input : A = { 1 , 3 , 2 }

output : 3.

Explanation :

=> Send 1 to index 1. (Cost +1)

A [3, 1, 2]

Send 3 to index 2. (Cost +2)

A = [1, 2, 3]

and the array is sorted.

hence total cost = 3.

Any approach for solving this problem>

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

First, find the largest suffix of the permutation that is in increasing order. For example for the array 3 6 5 1 2 4 7, the largest such suffix will be 1 2 4 7. Then we need to place only the elements 3 6 5 at their correct positions and the array will be sorted after that. For calculating the cost of shifting the element from 3 6 5, we can find the number of jumps we need to make in the sorted suffix plus the number of elements that are remaining in the 3 6 5 part. Say we placed 3 at its correct position. Now the cost will be 2 + 2, 2 moves for going beyond 6 5 and 2 again for going beyond 1 2. To calculate the latter we can use lower_bound on 1 2 4 7. Now we want to place 6 in the correct position. To calculate moves we can either modify our suffix 1 2 4 7, i.e. insert 3 in it and then repeat the same procedure or we can just add the number of elements before 6 which are less than 6 in the part 3 6 5, which can be done efficiently using Fenwick Tree or Segment Tree.
If you find any counter test then please inform.

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

    Yeah, this is correct

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

    what will you do in this case.

    3 6 10 5 8 9 11 1 2 4 7

    which suffix to take in this condition we we can have same suffix length at various positions.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      You can just take last element that $$$a{_i}$$$ < $$$a{_{i-1}}$$$ and the starting position would be $$$i$$$