### bhuvnesh97's blog

By bhuvnesh97, history, 2 years ago,

I just find this problem but couldn't think of a solution ??can anyone will help me??

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.

• -2

 » 2 years ago, # |   0 as $N$ and $K$ are really small you can just enumerate all permutations and build a graph based on that (a permutation is a vertex and two permutations are conected by an edge if they can be tranformed into each other). The answere can then be found with bfs.
•  » » 2 years ago, # ^ |   0 thank u very much!! I implemented it and its working .. my code link #include using namespace std; bool check(string s){ for(int i=1;i>n; char a[n+1]; for(int i=0;i>a[i]; a[n]='\0'; cin>>k; setvis; queue >per; per.push({a,0}); int ans=0; bool flag=false; // while(1){ // if(!flag){ while(!per.empty()){ auto left=per.front(); per.pop(); string s=left.first; int val=left.second; vis.insert(s); if(check(s)){ ans=val; flag=true; break; } string cp=s; for(int i=0;i<=n-k;i++){ auto str=rev(cp,i,i+k-1); if(vis.find(str)==vis.end()){ per.push({str,val+1}); } cp=s; } } // }else break; // } if(flag) cout<
•  » » » 2 years ago, # ^ |   0 It got Accepted -_-