[Solution] K Distinct Array solution codechef

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 integer NN and an integer KK such that NK(N+12)N≤K≤(N+12).

Construct an array AA of length NN that satisfies the following conditions

  • AA has exactly KK good (contiguous) subarrays, and
  • Every element of AA is an integer from 11 to NN (both inclusive).

K Distinct Array solution codechef

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

  • The first line contains an integer TT, the number of testcases. The description of the TT testcases follow.
  • Each testcase consists of a single line with two space separated integers, NN and KK respectively.

Output Format

  • For each testcase print NN 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 11 and NN, and
    • The array has exactly KK good subarrays

K Distinct Array solution codechef

  • 1T1051≤T≤105
  • 1N1051≤N≤105
  • NK(N+12)N≤K≤(N+12)
  • Sum of NN over all testcases is atmost 31053⋅105.

Sample Input 1 

5 5
5 15
5 7

Sample Output 1 

1 1 1 1 1
1 2 3 4 5
1 2 2 1 1

Explanation K Distinct Array solution codechef

Test Case 1: N=5,K=5N=5,K=5. All subarrays of length 11 are good, therefore every array of size NN has at least NN good subarrays. If all elements are equal then these will be the only good subarrays so the given array {1,1,1,1,1}{1,1,1,1,1} is a valid solution. Observe that under the constraints there are 55 different solutions (one for each value 11 through 55) and all of them will be considered correct.

Test Case 2: N=5,K=15N=5,K=15. There are only (N+12)=15(N+12)=15 subarrays, including the array itself. Therefore the array itself must be good which leads us to the solution given above. Any permutation of {1,2,3,4,5}{1,2,3,4,5} is also a valid solution, thus there are 5!=1205!=120 different solutions to this case and all of them will be considered correct.

Test Case 3: N=5,K=7N=5,K=7. The constructed array is A={1,2,2,1,1}A={1,2,2,1,1}. You may verify that the only good subarrays of AA, in addition to the 55 subarrays of length 11, are those shown below (subarrays are highlighted red).

  • {1,2,2,1,1}{1,2,2,1,1}
  • {1,2,2,1,1}

Leave a Comment