P A N C A K E Sorting
All submissions for this problem are available.
Pancake sorting is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible. This operation can be visualized by thinking of a stack of pancakes in which one is allowed to take the top K consecutive pancakes and flip them.
In this problem we will try to sort characters instead of pancakes. You are given a sequence of characters of length N and you are allowed only one operation (similar to the Pancake problem). However, instead of only the top K, here you are allowed to reverse any K consecutive elements of the sequence. Your goal is to sort the sequence in non-increasing order.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space separated integers N and K denoting the length of the sequence and number of consecutive element you can reverse. The second line contains N space-separated distinct lower case alphabets ('a'-'z') A1, A2, ..., AN denoting the character sequence you need to sort.
An integer denoting the minimum number of operations required for sorting the sequence or “NP” (quotes for clarity) if it is impossible.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 9
- 0 ≤ K ≤ N
4 3 2 d s l 7 5 u e q n f m g 2 2 a y 9 4 t j l a z i b y g
2 NP 1 NP
|Time Limit:||10 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.