[Solved] Yet another MEX problem codechef solution

October Challenge 2021 Division 3 (Rated) - CodeChef

Yet another MEX problem codechef solution

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

  • The MEX of [2,2,1][2,2,1] is 00, because 00 does not belong to the array.
  • The MEX of [3,1,0,1][3,1,0,1] is 22, because 00 and 11 belong to the array, but 22 does not.
  • The MEX of [0,3,1,2][0,3,1,2] is 44, because 0,1,20,1,2 and 33 belong to the array, but 44 does not.

You are given an array AA of length NN. You create a list BB consisting of the MEX-es of all subarrays of the array AA. Formally, for all pairs (l,r)(l,r) such that 1lrN1≤l≤r≤N, you calculate MEX(Al,Al+1,,Ar)MEX(Al,Al+1,…,Ar) and append the value in the list BB. Find the KK-th smallest value in the list BB.

Note: Since the size of the input and output is large, please use fast input-output methods.

Yet another MEX problem codechef solution

Input Format

  • The first line contains TT denoting the number of test cases. Then the test cases follow.
  • The first line of each test case contains two space-separated integers NN and KK.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN denoting the given array.

Yet another MEX problem codechef solution

Output Format

For each test case, output on a single line the KK-th smallest value in the list BB.

Yet another MEX problem codechef solution

Constraints

  • 1T31041≤T≤3⋅104
  • 1N1051≤N≤105
  • 1KN(N+1)2 1≤K≤N⋅(N+1)2 
  • 0AiN0≤Ai≤N
  • Sum of NN over all test cases does not exceed 21062⋅106.

Yet another MEX problem codechef solution

Subtasks

Subtask 1 (10 points):

  • 1N51031≤N≤5⋅103
  • Sum of NN over all test cases does not exceed 51045⋅104.

Subtask 2 (90 points): Original constraints

Yet another MEX problem codechef solution

Sample Input 1 

3
3 4
1 0 2
3 2
2 1 3
3 6
0 1 2

Sample Output 1 

1
0
3

Explanation

Test case 11: MEX(A1)=0MEX(A1)=0MEX(A1,A2)=2MEX(A1,A2)=2MEX(A1,A2,A3)=3MEX(A1,A2,A3)=3MEX(A2)=1MEX(A2)=1MEX(A2,A3)=1MEX(A2,A3)=1MEX(A3)=0MEX(A3)=0. Hence the list B=[0,2,3,1,1,0]B=[0,2,3,1,1,0] and the 44-th smallest value in BB is 11.

Test case 22: The MEX of all subarrays of the array AA is 00. Hence the 22-nd smallest element in the list BB is 00.


Updating Soon…


Yet another MEX problem codechef solution

Counting Tuples codechef solution

 

Leave a Comment