# SHUFFLE Editorial (LTIME83B) Unofficial

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
``````
4 Likes

Thank for the explanation but I think you should put unofficial in the title. Official editorial: SHUFFLE - Editorial

1 Like

Done!

1 Like