proving a greedy algorithm

Revision en1, by hiddentesla, 2016-07-05 07:25:11

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

Tags bfs, greedy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English hiddentesla 2016-07-05 07:25:11 1021 Initial revision (published)