Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### 444iq's blog

By 444iq, history, 7 months ago, ,

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>

• 0

 » 7 months ago, # |   0 Welcome to FAKEFORCES
•  » » 7 months ago, # ^ |   0 Problem matters.
 » 7 months ago, # | ← Rev. 2 →   +4 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.
•  » » 7 months ago, # ^ |   0 Yeah, this is correct
•  » » 7 months ago, # ^ |   0 what will you do in this case.3 6 10 5 8 9 11 1 2 4 7which suffix to take in this condition we we can have same suffix length at various positions.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +1 You can just take last element that $a{_i}$ < $a{_{i-1}}$ and the starting position would be $i$