bhuvnesh97's blog

By bhuvnesh97, history, 17 months ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank u very much!! I implemented it and its working .. my code link

    #include<bits/stdc++.h>
    using namespace std;
    bool check(string s){
        for(int i=1;i<s.length();i++)
            if(s[i]<s[i-1]) return false;
        return true;
    }
    string rev(string s,int i,int j){
        while(i<=j){
            swap(s[i],s[j]);
            i++;
            j--;
        }
        return s;
    }
    int main(){
        int n,k;
        cin>>n;
        char a[n+1];
        for(int i=0;i<n;i++)
            cin>>a[i];
        a[n]='\0';
        cin>>k;
        set<string>vis;
        queue<pair<string,int> >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<<ans<<endl;else
        cout<<-1<<endl;
    return 0;
    }