Puzzle on Sorting
Source: Saurabh Joshi's Blog
Problem: (copy-pasting from the source)
Suppose we have 13 cards arranged in descending order: K Q J 10 9 8 7 6 5 4 3 2 1
At any move, you can take a substring of cards and move it elsewhere. For example, 10 9 8 could be move to the right by 2 steps to get K Q J 7 6 10 9 8 5 4 3 2 1. The goal is to sort the string in increasing order minimize the number of such moves.
It must be absolutely obvious that you can do it with 12 moves but the very fact that I’m asking you this question means that you can do better. How many moves do you need?
Now the obvious extension to this problem is to generalize this technique for any n.
Awesome Problem!!
Update (Sep 07, 2010):
Solution: At Saurabh Joshi's blog (Link)
Problem: (copy-pasting from the source)
Suppose we have 13 cards arranged in descending order: K Q J 10 9 8 7 6 5 4 3 2 1
At any move, you can take a substring of cards and move it elsewhere. For example, 10 9 8 could be move to the right by 2 steps to get K Q J 7 6 10 9 8 5 4 3 2 1. The goal is to sort the string in increasing order minimize the number of such moves.
It must be absolutely obvious that you can do it with 12 moves but the very fact that I’m asking you this question means that you can do better. How many moves do you need?
Now the obvious extension to this problem is to generalize this technique for any n.
Awesome Problem!!
Update (Sep 07, 2010):
Solution: At Saurabh Joshi's blog (Link)
Why not simply try to follow a divide & conquer approach ?
ReplyDeleteMove n/2 elements from right to left end & solve these smaller n/2 & ceil(n/2) element sequences .
Number of moves :
Let T(n) denote number of moves using this algorithm for n numbers.
T(1)=0
T(n)= T(floor(n/2)) + T(ceil(n/2)) + 1
Solving this one can find T(n) & I know this recurrence is not "too" difficult to solve- I have solved it sometime back.
PS:As far as proving is concerned this is the best, I think we would be able to come up with an argument which would establish that sorting can be done in time less then O(nlogn). But again, I dont want to think right away.
@Nikhil.. Using the recurrence, all you get is this:
ReplyDeleteT(n) <= cn
which we already know. I want you to give me an algorithm, where T(n) <= n-1
K Q J 10 9 8 7 6 5 4 3 2 1
ReplyDeleteK 6 5 4 3 2 1 Q J 10 9 8 7
1 Q K 6 5 4 3 2 J 10 9 8 7
1 2 J Q K 6 5 4 3 10 9 8 7
1 2 3 10 J Q K 6 5 4 9 8 7
1 2 3 4 9 10 J Q K 6 5 8 7
1 2 3 4 5 8 9 10 J Q K 6 7
1 2 3 4 5 6 7 8 9 10 J Q K
i think this is not np hard either :D
m fan of Nikhil Garg myslef niraj
joined codechef and written to nikhil pls reply nikhil.