SPOJ GENERAL: sorting by swaps of distance k

Question

I have been trying to solve this simple problem on SPOJ for quite some time now, but I keep on getting TLE (Time limit exceeded) for some reason.

Since the problem is in Portuguese, a brief description of the problem is like this (without the story):

You are given an array of size N, you have to arrange the array in ascending order, such that an element can only be swapped with elements which are at a distance k from it. If the array can be sorted then print the number of swaps required to arrange them in ascending order, if it cannot be sorted print impossivel.

This is my code:

#include <iostream>
#include <cstdio>

using namespace std;
int a[100005];
int main() {
    int t;
    int n, k;
    scanf("%d", &t); //number of test cases
    while(t--) {
        scanf("%d %d", &n, &k);
        bool result = true;
        int count = 0;

        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }

        for(int i = n; i > 0; i = i - k) {
            int j = 0;
            for( ; j < i - k; j++) {
                if(a[j] > a[j + k]) {
                    int temp = a[j];
                    a[j] = a[j + k];
                    a[j + k] = temp;
                    count++;
                }
            }

            for( ; j < i - 1; j++) {
                if(a[j] > a[j + 1]) {
                    result = false;
                    break;
                }
            }

            if(!result)
                break;
        }
        if(result)
            printf("%d\n", count);
        else
            printf("impossivel\n");
    }
}

My logic : I perform N/k iterations on the array. I initialize the loop variable i to N. In each iteration I check i-k elements with the element at a distance k from it, if they are to be swapped then I swap them and increment the number of swaps needed, else I do nothing. Then I check the elements from i-k to i, if they are in ascending order, if not I break the loop and print "impossivel", else I change i to i-k and again perform the loop. By my logic after every iteration the last k elements will be in ascending order, if is possible to sort them, since at every step I move the elements which are greater to the right.

Does this seem correct to you? How can optimize this further?

Answer 1

The above code can be optimized a little by below changes.

Replace this

        for( ; j < i - k; j++) {
            if(a[j] > a[j + k]) {
                int temp = a[j];
                a[j] = a[j + k];
                a[j + k] = temp;
                count++;
            }
        }

        for( ; j < i - 1; j++) {
            if(a[j] > a[j + 1]) {
                result = false;
                break;
            }
        }

        if(!result)
            break;

By

        int  j = i-k;
        int x = 0;
        int tmp[i/k]; // Do check for i==0 here 
        for(int j = i; j >= 0; j -= k){
            tmp[x] = a[j];  
            x++;
        }
        sort(tmp);
        for(int j = i; j >= 0; j -= k){
             a[j] = tmp[x]; x--; 
        }

Add a check outside the main loop if its sorted or not. But still this will be in order of \$O(N*KlogK)\$ which in worst cases \$O(N^2logN)\$. You might still get the TLE with that.

We can solve this in \$O(NlogN)\$. Trying thinking of solution in which you sort this a keeping original indexes of each element. Then calculate the number of swap by comparing the old index with new one.