hiddentesla's blog

By hiddentesla, history, 8 years ago, In English

short problem statement:

given N and K (2 <= N,K <= 8) and an array consisting of N distinct elements; in one move you can pick a block of K elements in the array and reverse the order, for example: if N = 5 and K = 3 and the array is [4 5 1 2 3], in one move you can make the array [1 5 4 2 3] or [4 2 1 5 3] or [4 5 3 2 1]. how many minimum number of moves is required to make the array sorted in ascending order?, if impossible, print -1.

i cant give a link to the problem, because its in my native languange's, so i thought of a greedy algorithm:

for each i, find the i'th smallest element and perform BFS until that element is in the i'th position

my implementation: https://ideone.com/3x2vwP

however, it seems that this greedy algorithm do not always work, but im having troubles finding a counter case, can someone provide me one?

note: since the constraints are very low, i did a full frontal BFS and got AC: https://ideone.com/SYJklC . but im still curious...

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

8 years ago, # |
  Vote: I like it +28 Vote: I do not like it