K Distinct Array solution codechef
An array is said to be good if all its elements are distinct, i.e. no two elements of the array are equal to each other.
You are given a positive integerand an integer such that .
Construct an arrayof length that satisfies the following conditions
- has exactly good (contiguous) subarrays, and
- Every element of is an integer from to (both inclusive).
If there are multiple such arrays, you can print any of them.
Note: It can be shown that for all inputs satisfying the given constraints, there is always a valid solution.
Input Format K Distinct Array solution codechef
- The first line contains an integer , the number of testcases. The description of the testcases follow.
- Each testcase consists of a single line with two space separated integers, and respectively.
- For each testcase print space separated integers, the elements of the constructed array.
- If there are multiple outputs, you can print any of them.
- Your output will be considered correct only if the following conditions are satisfied,
- Every element of the array is between and , and
- The array has exactly good subarrays
Constraints K Distinct Array solution codechef
- Sum of over all testcases is atmost .
Sample Input 1
3 5 5 5 15 5 7
Sample Output 1 K Distinct Array solution codechef
1 1 1 1 1 1 2 3 4 5 1 2 2 1 1
Test Case 1:. All subarrays of length are good, therefore every array of size has at least good subarrays. If all elements are equal then these will be the only good subarrays so the given array is a valid solution. Observe that under the constraints there are different solutions (one for each value through ) and all of them will be considered correct.
Test Case 2:. There are only subarrays, including the array itself. Therefore the array itself must be good which leads us to the solution given above. Any permutation of is also a valid solution, thus there are different solutions to this case and all of them will be considered correct.
Test Case 3:. The constructed array is . You may verify that the only good subarrays of , in addition to the subarrays of length , are those shown below (subarrays are highlighted red).