[Solution] Equal Mex Splitting solution codechef – Chef has an array AA of length NN. Chef wants to select some disjoint, non-empty subarrays from AA

Equal Mex Splitting solution codechef – Chef has an array AA of length NN. Chef wants to select some disjoint, non-empty subarrays from AA such that:

  • The mexmex of each of the selected subarray is the same.

Note that the selected subarrays need not cover all the elements of the array.

For e.g. if A=[2,0,1,6,2,1,3,0,7]A=[2,0,1,6,2,1,3,0,7], then one way in which Chef can select subarrays is as following: [0,1],[1,3,0][0,1],[1,3,0] (Here mexmex of both of them is 22).

Equal Mex Splitting solution codechef

Chef wants to select the maximum number of disjoint, non-empty subarrays that satisfy the above condition. Can you help him to do so?

Note: An array XX is called a subarray of an array YY if XX can be obtained from YY by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Also, mexmex of a subarray is the smallest non-negative number that does not occur in that subarray.

Input Format

  • The first line will contain TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains a single integer NN – the length of the array AA.
  • The second line of each test case contains NN space-separated integers – A1,A2,,ANA1,A2,…,AN denoting the array AA.

Output Format

For each test case, output the maximum number of disjoint subarrays which Chef can select such that mexmex of each subarray is the same.

Equal Mex Splitting solution codechef

  • 1T10001≤T≤1000
  • 1N1051≤N≤105
  • 0AiN0≤Ai≤N
  • It is guaranteed that the sum of NN does not exceed 51055⋅105

Sample Input 1 

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

Sample Output 1 

2
3

Equal Mex Splitting solution codechef

Test case-1: Chef can select the following subarrays: [0,1][0,1][1,0][1,0]. Here mex([0,1])=mex([1,0])=2mex([0,1])=mex([1,0])=2. Therefore the answer is 22.

Test case-2: Chef can select the following subarrays: [0][0][0,3][0,3][2,0][2,0]. Here mex([0])=mex([0,3])=mex([2,0])=1mex([0])=mex([0,3])=mex([2,0])=1. Therefore the answer is 33.

For solution

Click here

Leave a Comment