1

Problem Statement -

Problem Statement

The task is to find the minimum number of swaps required in the given arrangement of cartons to get the desired arrangement of cartons. Only adjacent cartons can be swapped.

I have tried an ad hoc approach, but it proved inefficient towards the upper limit of the data range. Here it is for reference - 

Traversing through the given arrangement of cartons
 if position of carton>than the desired position
  swap back
  go to previous iteration

What would be a pragmatic approach to the problem?

Test Data Range - N<=105

Source - INOI 2009 Q Paper

Improve this question
6
  • in other words you want to find the most efficient bubblesort...
    – ratchet freak
    Commented Dec 25, 2012 at 23:54
  • 1
    Reason for down-voting? @ratchetfreak I find bubblesort per se inefficient. I am trying to find an algorithm that can handle such large data-sets in an efficient way.
    – 7Aces
    Commented Dec 26, 2012 at 5:29
  • 1
    @ratchet freak: I am not sure this is bubble sort: in bubble sort you repeatedly scan an array and perform the swaps during each scan. Here you want to find a minimal sequence of swaps that produces a solution. Seems like a problem that can be solved using streams and lazy evaluation.
    – Giorgio
    Commented Dec 26, 2012 at 10:26
  • 1
    @7Aces: I also do not understand the down vote and the votes to close. The question is very clear (and IMHO, interesting too): find an algorithm that computes an optimal solution. Upvoting and voting to keep open.
    – Giorgio
    Commented Dec 26, 2012 at 10:28
  • Here is the solution - stackoverflow.com/questions/7797540/…
    – Petar Minchev
    Commented Dec 26, 2012 at 10:34

1 Answer 1

Reset to default
1

with only adjacent swaps you are limited to a O(n^2) sorting algorithm, (with worst case being a reverse sorted set)

and since you only have to limit yourself to least amount of swaps you can compare everything as much as you like

one way to guarantee the least amount of swaps is to only swap 2 cartons when they are in reverse order

both bubble sort and insertion sort will do this

the way to compute this minimum is to find the desired location of each carton (with any sorting algo) and take the sum of the amount each carton is shifted and divide by 2

in psuedo code

sort arr
sum=0
foreach c in arr
   sum+= abs(oldIndexOf(c)-indexOf(c))
return sum/2
Improve this answer
3
  • An algorithm with a O(n^2) time complexity is just not efficient enough to solve the data ranges in the time limit. The most efficient algorithm for this possesses O(n log n) time, see - stackoverflow.com/questions/7797540/…. The algorithm provided resorts to O(n^2) complexity as it finds oldindex(c) with every iteration.
    – 7Aces
    Commented Dec 26, 2012 at 15:30
  • 1
    @7Aces, oldindex(c) is an O(1) operation if you store it in a hash table.
    – Karl Bielefeldt
    Commented Dec 26, 2012 at 16:13
  • 1
    @KarlBielefeldt Thanks for the tip! Still, incorrect algorithm. Gives incorrect output for the test case - O={1,2,3,4,5,6} R={6,5,4,3,2,1}. Output - 9 (Should be 15)
    – 7Aces
    Commented Dec 26, 2012 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.