Блог пользователя Pancake

how to obtain a bound on this problem ?

Автор Pancake, 12 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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}.

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

Where did you find this problem?

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

→ Ответить