Atamyrat Hezretguliyew wrote: > http://web.mit.edu/~mip/www/probs.html > > [12] Sorting by reversals (ONI'04) > You are given an array A[1..N]. Your goal is to sort A by the > following type of operation: pick some indices i,j and reverse the > subarray A[i..j]. Such an operation costs j-i+1, i.e. the length of > the portion which is reversed. Your sorting algorithm should have a > total cost of O(N lg^2 N).
This is a nice problem, but not the one the OP was asking about. This version allows flips of the form i..j instead of only 0..j. Also, the cost per flip is |i - j| instead of 1. The original problem is known as the "pancake problem", perhaps best known because Bill Gates (and Christos Papadimitriou) have a paper on it. The following link provides some useful info. http://www.math.uiuc.edu/~west/openp/pancake.html --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
