Problem Link: CodeChef: Practical coding for everyone
The trick is to realize that the problem is equivalent to dividing the array A in K subarrays, sort them individually and then check if the final array is sorted.
The i^{th} subarray will have elements at indices: i, i+K, i+2K, .... Since we can swap elements at these indices only, we see that each subarray can be sorted. (Proof: Sorting each subarray is equivalent to performing bubble sort on it).
After sorting each subarray, we check if the final array is sorted or not.
For example:
Let A = [10, 1, 8, 7, 20, 2, 9] and K = 3
Our subarrays will be:
A1 = [10, 7, 9]
A2 = [1, 20]
A3 = [8, 2]
Sorting them will give
A1 = [7, 9, 10]
A2 = [1, 20]
A3 = [2, 8]
Our final Array would be:
A = [7, 1, 2, 9, 20, 8, 10] which is not sorted, so the answer is no.
Note that while coding, we have to take care of the fact that there can be unequal elements in the subarrays.
Accepted Code:
t = int(raw_input()) while t!=0: n, k = map(int, raw_input().split()) a = map(int, raw_input().split()) if k==1: print "yes" t-=1 continue L = [] for i in range(k): j = 0 x = [] while k*j+i<n: x.append(a[k*j+i]) j+=1 x = sorted(x) L.append(x) A = [] j = 0 for j in range(n/k): for i in range(k): A.append(L[i][j]) for i in range(n%k): A.append(L[i][-1]) possible = True for i in range(len(A)-1): if A[i]>A[i+1]: possible = False break if possible==True: print "yes" else: print "no" t-=1