Pancake's blog

how to obtain a bound on this problem ?

By Pancake, 12 years ago, In English

Hello All . I have recently encountered the following problem : "Given is a permutation of the integers {1, 2, ..., N} where 1 <= N <= 50 . We are allowed to perform as many operations as we wish of the form : pick any subsequence consisting of exactly K consecutive elements , and reverse the order of these elements . What is the least number of operations needed to sort the permutation in increasing order?". Some contestants solved this problem using a mere BFS , and got it accepted . They say that it works because there's a reasonable limit on the states the original permutation can be converted to. Is that correct ? May someone help me find this bound ? Thanks.

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

»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Not a correct solution but a simplest way to prove your bounds =) When we are reversing a[j]..a[j+k-1] i-th element goes to 2*j-i+k-1 position. So we can in a dumb way restore path of 1: try all possible values of j and i in each step. There would be less then n steps (because if correct solution exists => there is no cycles and only n different positions). And then apply same algo to new permutation of n-1 elements (beginning from 2). So, it will be O(n^4) operations — it's less 1 sec, when n<=50 =)

P.S. But there can be no solution. For example: n=5, k=3, a={2,1,3,5,4}.

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

Where did you find this problem?

It's actually Sorting Permutation by Reversals, which is NP-Hard.

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

If K = 2 and initial permutation is {N, N - 1, ..., 1} then all permutations can be reached and sorted permutation needs the largest number of reversals, so BFS will reach all N! states.

Maybe, in your problem it was guaranteed that answer is small?

→ Reply