Arrays Sum SOLUTIONS GRAKN FORCES 2020

Arrays Sum SOLUTION

You are given a non-decreasing array of non-negative integers a1,a2,…,an. Also you are given a positive integer k.
You want to find m non-decreasing arrays of non-negative integers b1,b2,…,bm, such that:
The size of bi is equal to n for all 1≤i≤m.
For all 1≤j≤n, aj=b1,j+b2,j+…+bm,j. In the other word, array a is the sum of arrays bi.
The number of different elements in the array bi is at most k for all 1≤i≤m.
Find the minimum possible value of m, or report that there is no possible m.
Input
The first line contains one integer t (1≤t≤100): the number of test cases.
The first line of each test case contains two integers n, k (1≤n≤100, 1≤k≤n).
The second line contains n integers a1,a2,…,an (0≤a1≤a2≤…≤an≤100, an>0).
Output
For each test case print a single integer: the minimum possible value of m. If there is no such m, print −1.
Example
inputCopy
6
4 1
0 0 0 1
3 1
3 3 3
11 3
0 1 2 2 3 3 3 4 4 4 4
5 3
1 2 3 4 5
9 4
2 2 3 5 7 11 13 13 17
10 7
0 1 1 2 3 3 4 5 5 6
outputCopy
-1
1
2
3
3
1
Note
In the first test case, there is no possible m, because all elements of all arrays should be equal to 0. But in this case, it is impossible to get a4=1 as the sum of zeros.
In the second test case, we can take b1=[3,3,3]. 1 is the smallest possible value of m.
In the third test case, we can take b1=[0,1,1,1,2,2,2,2,2,2,2] and b2=[0,0,1,1,1,1,1,2,2,2,2]. It’s easy to see, that ai=b1,i+b2,i for all i and the number of different elements in b1 and in b2 is equal to 3 (so it is at most 3). It can be proven that 2 is the smallest possible value of m.
In the fourth test case, we can take b1=[0,0,0,1,2], b2=[0,0,1,1,1], b3=[1,1,1,1,1]. It’s easy to see, that ai=b1,i+b2,i+b3,i for all i and the number of different elements in b1, in b2 and in b3 is at most 3. It can be proven that 3 is the smallest possible value of m.

Leave a Comment