Found it in collection of Jian Li, CS Department, University of Maryland
Given 2 cyclic strings, both consisting n distinct letter,namely a permuatation of 1 to n.
the problem is to find a rotation of one string that minimize the swap distance.(i.e.the number of swaps of adjacent elements to bring one necklace to the other)
Can you give an O(nlogn) algorithm?
This is a difficult problem. So, think hard!!
Update (11/12/09): Solution in comments !!
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Post Comments (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...
Step1: Realise that this problem can be converted into a simpler problem. By renumbering the numbers, I can always convert the problem to an equivalent problem where find the number of rotations such that the number of adjacent swaps required is minimum...
ReplyDeleteAlso note that no. of adjacent swaps is number of moves required in bubble sorting method. This is equivalent to calculating the number of inversion pairs in an nlength array.
Step2: The plan is to first calculate number of inversion pairs initially in O(nlog n). Then corresponding to each rotation, with O(nlog n) preprocessing time, we can find the number of inversion pairs in O(1). So, this is O(n logn) + O(n). Finding the minimum is O(1). So, the algorithm is O(nlog n)
Done in many advanced algorithms courses, this problem can be solved by using divide and conquer in O(n log n).
This makes use of calculating the number of inversion pairs in two halves independently. "Conquering" is done by calculating the number of inversion pairs with left end in left part and right end in right part. This can be calculated and is a byproduct of merge sort algorithm. We get an O(n log n) algorithm to calculate the number of swaps.
Now left is to give an algorithm to calculate number of inversion pairs in Permutation P2 from number of inversion pairs in Permutation P1, where P1 on cyclic rotation gives P2. Note that the only difference the two have is that the first number has moved to last. So, if we know the rank of the number in a sorted list, we can get it in O(1). Thats the O(n logn) preprocessing time we talked about. :)
So, answer.
Anyone can write it in a better way? Thanx
Here, you have not considered that we can swap the first and last element. In that case, number of swaps required can be lesser than the number of inversions.
ReplyDeleteeg. has 2n2 inversions but by a single swap of n and 1, we get the correct permutation. I think the method of inversion pairs cannot be used in the above scenario.