hasanb's blog

Can we sort the array with reverse?
By hasanb, history, 9 years ago, In English

The problem is what's the minimum amount of reverse so the array become sorted. I observed in the worst case answer is N-1. But how can I solve the problem?

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did you come to the conclusion that the worst case is N?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

    I think it's based on that the worst case would be you having to make a reverse in order to put every single element in it's place. For example: 2 3 1

    First, you see the number 1 is in the wrong position so you use a reverse to make it 1 3 2

    Second, you see the number 2 is in the wrong position so you use a reverse to make it 1 2 3

    So, at most you will need N — 1 operations on the worst case, following this strategy: For each element which is not in it's right place, reverse a segment starting with the index where you want to put the number, and ending with the index the number is currently at.

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it -17 Vote: I do not like it

Find i, such that ai is the smallest element of array a among index 1 to n. Then if you reverse a1 to ai, you have the smallest element of a at a1. Again, find the smallest among a2 to an and reverse a2 to ai to bring the 2nd smallest to the 2nd position... and so on...

UPD: This will sort the array using exactly n reverses. Minimum number of needed reverses may be less. So this does not help you finding minimum number of reverse operations. It's only useful if you are allowed to do up to n reverse operations.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    This can be done efficiently using treap in O(NlogN) time.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I posted this solution based on the observation of the author of the blog, which says he may do up to N reverse operations. I didn't know there exists better solutions, thank you for mentioning.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Counter-example: 5 1 2 3 4
    Answer is 2 (reverse [2, 5] and reverse [1, 5])

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      Let's run this algorithm another time, but sorting in decreasing order (:

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +55 Vote: I do not like it

What can you reverse?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Second is my problem. So I understand we can't solve the problem in exponential time complexity. Am I wrong?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      We can't solve the problem in polynomial time complexity. We can pretty much always solve problems in exponential time complexity.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Thanks

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it -21 Vote: I do not like it
        "We can pretty much always solve problems in exponential time complexity."

        Actually we can't, most problems are undecidable.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          What do you mean by "most"? It's very rare that I see an undecidable problem and most of them are very abstract. For the majority of the problems with finite constraints you can just apply the dumbest bruteforce and get a terribly slow but correct solution (perhaps with exponential memory, too).

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            nope

            P.S. Codeforces downvoters are like a flock of sheep.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              Yes, there are more real non-integer numbers than integers. Though, there are almost only decidable problems in the competitive programming.

              PS. Don't expect upvotes after writing that downvoters are bad/stupid/etc. It doesn't work this way.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it -15 Vote: I do not like it

                I'm only expecting votes :D

                → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This problem asks what you want. Sort the array with maximum n swaps.

I solved this problem using method similar to selection sort.

Start from first index, find minimum element in the array then swap it with first index. Do same for other indexes. Maximum n swaps.

Code

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

As linked by cgy4ever your problem is the pancake flipping problem which is NP-Hard, sadly. Anyone who proposes some solution that is polynomial here is most likely wrong.

→ Reply