SPOJ: GENERAL (Time limit exceeded)

Question

I have been trying to solve this simple problem (http://br.spoj.com/problems/GENERAL/) 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? Thanks for any help in advance. :)

You'll probably have a better response posting on [Code Review](http://codereview.stackexchange.com/) — Steve Lorimer, Jun 27 '16 at 16:53
You used a bubble sort algorithm, one of the worst ones to use in terms of time complexity. — PaulMcKenzie, Jun 27 '16 at 17:13
You could use some profiling tool like `gprof` to identify where your bottlenecks actually are. — πάντα ῥεῖ, Jun 27 '16 at 17:18
Also, is it necessary to show the code that asks for the input and the `while` loop doing this? Why not first write the "meat" of the code first, you know, the part that actually solves the problem, in some sort of a function that you can test? I see this over and over again with these SPOJ posts -- all the input routine adds is clutter. — PaulMcKenzie, Jun 27 '16 at 17:22
@PaulMcKenzie: with the requirement, OP cannot use other sort. — Jarod42, Jun 27 '16 at 17:38
@PaulMcKenzie According to the problem constraint array elements at a distance **k** can be exchanged, so I cannot use any other sorting algorithm. — user007, Jun 27 '16 at 17:45
@user007 -- Then you are going to be hard-pressed in getting better results if you're stuck with basically a quadratic, `O(n*n)` solution, which is what a bubble sort gives you. So basically your requirements are to use the worst sorting technique out there, but make the code fast? — PaulMcKenzie, Jun 27 '16 at 17:51
Your current title, "SPOJ: GENERAL (Time limit exceeded)", says nothing about the problem you're trying to solve. The people who can help you probably don't care about SPOJ (the web site that's the source of the exercise). I suggest updating the title to describe the actual problem you're trying to solve. — Keith Thompson, Jun 27 '16 at 18:51

score 3 · Accepted Answer · edited May 23 '17 at 10:28

3

Separate into k sublists of n/k elements each.

Check impossibility condition.

Impossibility condition

Let k = 2 ,

3 4 1 2 is the array

For n/k lists maintain array to see if a number is present in O(1).

For eg. at spaced interval of 2

We can divide into two sublists , 3 1 and 4 2 Now we know sorted is

1 2 3 4 (Use counting sort as heights between 1 and n O(n))

So , we expect 1 at first place. Now ask , can 1 come here? If only it is in sublist.[Y]

If [N] say "impossible"

If impossible we are done else continue.

k times Merge sort, k * n/k(log(n/k))

(The number of inversions is equal to the minimum number of adjacent swaps to sort an array [known property] refer: Sorting a sequence by swapping adjacent elements using minimum swaps )

complexity of approach is n log n , which will easily pass :)

edited May 23 '17 at 10:28

Community

1
1

answered Jun 27 '16 at 18:44

Ishan

46
4

I was thinking the same general idea in breaking up the array into smaller lists, but did not work out details any further. The OP's answer of using a bubble sort was definitely not the way to approach this problem. – PaulMcKenzie Jun 27 '16 at 19:04
for `{5, 2, 3, 4, 1}` with a swap dist of `4`, res is 1, not number of inversion. – Jarod42 Jun 27 '16 at 20:00
@Jarod42 Separating into lists. First with gap of 4 : 5,1 Then 2 , Then 3 Then 4. [As next with gap of 4 not available] Sum of number of inversions is 1+0+0+0 which is the answer. Do let me know if it is clear now :) – Ishan Jun 27 '16 at 20:16
@Ishan Thanks :) That was great help. – user007 Jun 27 '16 at 21:20

SPOJ: GENERAL (Time limit exceeded)

1 Answers1

Linked