My appraoch is finding cycles.

1.if element is at its respective index ,we need to do nothing

2.Suppose for elements in the queue be 2 1, then one swap is

needed. accounting to 1 bribe

3.if elements in queue are 2 5 3 4 1 then 2 bribes are

needed.as 2->5->1 .

4.if that cycle increases ,then terminate .

5.Else output the total bribes count .

What is wrong with my approach . Pls explain....

code : http://ideone.com/N9E8QO

can somebody please tell me what is wrong with this code? int main(){ int t; cin >> t; while(t--) { int n,temp,bribes=0; int flag=0; cin >> n; int count_swap[n]; vector q(n); for(int q_i = 0;q_i < n;q_i++) { cin >> q[q_i];

    }
    for(int i=0,j=i+1;i<n,j<n;i++,j++)
    {

             count_swap[i]=0;
            if(q[i]<q[i+1])
               { temp=q[i];
                q[i]=q[i+1];
                q[i+1]=temp;
                bribes++;


                count_swap[q[i]]=count_swap[q[i]]+1;
               } 

    }


    for(int i=0;i<n;i++)
        {
      if(count_swap[i]>2)  
        flag=1;

    }
    if(flag==1)
    cout<<"Too chaotic"<<endl;
    else cout<<bribes<<endl;
    }



return 0;

}

TestCase 2: I/P ==>1 2 5 3 7 8 6 4 O/P ==>7

Acc to qn, a person can swap only with the person in front of him and max of 2 swaps are only allowed.

Hence, person 4 has moved to 8th position which is impossible. So, above solution should be "TOO CHAOTIC" only. How answer "7" is arrived ?

Is there anything worng in test case or is my logic wrong?

Counted the number of inversions for every element. Times out on 4 cases, how to improve it?

public static int calsum(int[] arr, int index){
    int temp = arr[index];
    int count = 0 ;
    for(int j=index+1 ; j<arr.length ; j++){
        if(arr[j]<temp){
            count++;
        }
        if(count>2){
            count=-1;
            return -1;
        }
    }
    return count;
}
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int T = in.nextInt();
    for(int a0 = 0; a0 < T; a0++){
        int n = in.nextInt();
        int q[] = new int[n];
        for(int q_i=0; q_i < n; q_i++){
            q[q_i] = in.nextInt();
        }
        int sum = 0;
        int tsum = 0;
        for(int i =0; i<q.length; i++){
            tsum = calsum(q,i);
            if(tsum==-1){
                break;
            }
            else{
                sum+=tsum;
            }
        }
        if(tsum==-1){
            System.out.println("Too chaotic");
        }
        else{
            System.out.println(sum);
        }
        // your code goes here
    }
}

Hi All, I have followed the naive approach.. It takes the time n2... Here is me code... Could you suggest me how I can increase the effeciency and solve it in O(n).. I am able tos olve 60%...

include

using namespace std;

int main(){

long long int n,m,i,j,t;
cin>>t;
while(t--){
cin>>n;
long long int a[n],g[n],last=0,final=0;
int c=0;
for(i=0;i<n;i++){
    cin>>a[i];
}
for(i=0;i<n-1 && c==0 ;i++){
    for(j=i+1;j<n;j++){
        if(a[i]>a[j]) last++;
        if(last>2) break;
    }
    if(last>2){
        //cout<<"too chaotic "<<last<<endl;
        c=1;
        last=0;
    }else{
        final=final+last;
        last=0;
    }
}
if(c==0)
    cout<<final<<endl;
else{
    cout<<"Too chaotic"<<endl;
}
}
return 0;

}