Sort a permutation minimizing the total cost of moves
Difference between en1 and en2, changed 8 character(s)
Hello everyone, I found this problem a while ago and I'm still stuck on it (there's no OJ to submit it as far as I know):  ↵
You are given a permutation of the integers from 1$1$ to N$N$. In this case, _moving_ an element from $i$ to $j$ is defined as removing the element from position i$i$, and inserting it at position j$j$. For example, in this array: `[4,5,2,1,3]`, moving the element from 2 to 5 gives us the array `[4,2,1,3,5]`. The cost of moving an element from $i$ to $j$ is defined as $i+j$ (1-indexed). What is the minimum total cost needed to sort the permutation?  ↵
Example:↵
`[1,3,4,5,2]` -> `[1,2,3,4,5]` with total cost $5+2=7$.  ↵
$1 \leq N \leq 1000$, however solutions with any reasonable complexity are welcome.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English f2lk6wf90d 2017-12-31 08:38:56 4 Tiny change: 'ment from 2 to 5 gives us ' -> 'ment from $2$ to $5$ gives us '
en5 English f2lk6wf90d 2017-12-31 01:35:00 3 Tiny change: '3,4,5,2]` -> `[1,2,3,4' -> '3,4,5,2]` → `[1,2,3,4'
en4 English f2lk6wf90d 2017-12-30 22:49:59 2 Tiny change: 'as $i+j$ (1-indexed).' -> 'as $i+j$ ($1$-indexed).'
en3 English f2lk6wf90d 2017-12-30 19:43:14 5 Tiny change: '\nExample:\n`[1,3,4,' -> '\nExample: \n`[1,3,4,'
en2 English f2lk6wf90d 2017-12-30 16:27:07 8
en1 English f2lk6wf90d 2017-12-30 02:57:47 774 Initial revision (published)