My three-year old has a set of rings of different sizes, each fitting
on a wooden peg, with all the pegs arranged in a row. He likes to
arrange the rings on the row of pegs in order of increasing size. He
likes to arrange the rings on the row of pegs in order of increasing (or
decreasing) size. He has exactly the same number of pegs and rings,
and has figured out that even if the rings are not in order to begin
with, by repeatedly swapping two adjacent rings, suitably selected, he
can order them.
Since he is something of a mathematical prodigy, at least in a fond father’s eyes, I gave him a challenge — he is only allowed to swap rings that are a fixed distance K from each other i.e. he gets to pick a ring, then swap it with one K positions before or K positions after. K=1 means the next ring before or after. Of course, this can be done only if there is a peg K positions away.
As I increased the number of rings and pegs in my kid’s toy, I realized that he will throw a tantrum if I give him an unsolvable problem, or one that will take too long to sort. So your task is to tell me how many swap operations are required to sort the rings.
Input:
The first line contains T, the number of test cases. Then, T test cases follow.
The first line of each test case contains 2 integers N and K, N being the number of rings.
The second line contains N integers denoting a1, a2, …., aN, where the a’s are the diameters of the rings. Values may be repeated.
1 <= K, N <= 500
1 <= T <=50
a[i] <= 1,000,000,000
Output:
Output must contain T lines, one per test case.
If it is possible to sort the array, output the minimum number of operations required, otherwise output “-1″.
Sample Input:
3
3 2
3 2 1
3 2
3 1 2
5 2
8 2 5 7 1
Sample Output:
1
-1
3
Since he is something of a mathematical prodigy, at least in a fond father’s eyes, I gave him a challenge — he is only allowed to swap rings that are a fixed distance K from each other i.e. he gets to pick a ring, then swap it with one K positions before or K positions after. K=1 means the next ring before or after. Of course, this can be done only if there is a peg K positions away.
As I increased the number of rings and pegs in my kid’s toy, I realized that he will throw a tantrum if I give him an unsolvable problem, or one that will take too long to sort. So your task is to tell me how many swap operations are required to sort the rings.
Input:
The first line contains T, the number of test cases. Then, T test cases follow.
The first line of each test case contains 2 integers N and K, N being the number of rings.
The second line contains N integers denoting a1, a2, …., aN, where the a’s are the diameters of the rings. Values may be repeated.
1 <= K, N <= 500
1 <= T <=50
a[i] <= 1,000,000,000
Output:
Output must contain T lines, one per test case.
If it is possible to sort the array, output the minimum number of operations required, otherwise output “-1″.
Sample Input:
3
3 2
3 2 1
3 2
3 1 2
5 2
8 2 5 7 1
Sample Output:
1
-1
3
No comments :
Post a Comment