1 3 2 5 4,
and without cycling and stuff, so we're trying to convert it to
1 2 3 4 5
you'll notice the optimal answer is 2 - changing 3 and 2, and 5 and 4. So they're disjoint, as in, they don't depend on each other.

Let's look at a more complicated example:
3 1 2 5 7 6 4 edit:
converting the above to 1 2 3 4 5 6 7. The optimal answer is actually 2, but I just wanted to demonstrate an example. Sorry for any confusion.

You can break it down to getting:
3 1 2 -> 1 2 3
and
5 7 4 -> 4 5 7

in which the total cost is 4, since the 6 is in the right spot.

Basically, it boils down to finding these "cycles", and just sum up the cost. You can do this in linear time given an array, since you can argue that each element won't be moved more than once, if you do it correctly. N iterations of shifting/reversing, and that's an O(n^2) algorithm.

I don't know if I made it clear enough, but if not, do ask.

Last edited by Larry on Thu Oct 16, 2003 1:56 pm, edited 1 time in total.

Larry wrote:Basically, it boils down to finding these "cycles", and just sum up the cost. You can do this in linear time given an array, since you can argue that each element won't be moved more than once, if you do it correctly. N iterations of shifting/reversing, and that's an O(n^2) algorithm.

Nitpick: that's not strictly true (e.g. if we want to go from 2 3 1 to 1 2 3, some element has to be moved twice).
(you still get the same time complexity though, O(N) to check how many swaps are needed to reach a specific final position, and 2N possible final positions.)

Does it mean that, now the 4 aliens sit around the table such that
alien 2 is next to alien 3 and alien 4
alien 3 is next to alien 2 and alien 1
alien 1 is next to alien 3 and alien 4
alien 4 is next to alien 1 and alien 2

And I need to do the minimum number of operations to exchange 2 aliens
(even they are not adjacent) so that
alien 2 is next to alien 3 and alien 1
alien 3 is next to alien 2 and alien 4
alien 1 is next to alien 4 and alien 2
alien 4 is next to alien 1 and alien 3??

Am I correct?? My program get WA for using 0.02s, much shorter than every accepted program. I think I have wrong understanding. Otherwise this problem should be solved in O(n)........

Last edited by .. on Mon Dec 22, 2003 7:49 pm, edited 1 time in total.

My signature:

Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.