Beautiful Subsequence solution codechef

Beautiful Subsequence solution codechef


An array AA consisting of NN integers is called KK-beautiful if it holds the following property: The number of adjacent indices with different values is at most KK. More formally, there are at most KK indices ii (1i<N1≤i<N) such that AiAi+1Ai≠Ai+1. Note that according to this definition, if an array AA is KK-beautiful, then AA is also (K+1)(K+1)-beautiful.

You are given an array AA consisting of NN integers and an integer KK. Find the length of the longest KK-beautiful subsequence of AA, where a subsequence is defined below.

For example, consider the array A=[1,1,2,3,2,4]A=[1,1,2,3,2,4]. The subsequences [1,1][1,1] and [1,1,2][1,1,2] are 11-beautiful, and the subsequences [1,2,3][1,2,3] and [1,2,2,4][1,2,2,4] are 22-beautiful.

Note:

  • A sequence aa is a subsequence of a sequence bb if aa can be obtained from bb by deletion of several (possibly, zero) elements. For example, [3,1][3,1] is a subsequence of [3,2,1][3,2,1] and [4,3,1][4,3,1], but not a subsequence of [1,3,3,7][1,3,3,7] and [3,10,4][3,10,4].

Input Format

The first line contains an integer TT – the number of test cases. Then TT test cases follow.

The first line of each test case contains two integers NNKK – the length of array AA and the parameter for a beautiful sequence.

The second line of each testcase contains NN integers A1,,ANA1,…,AN.

Output Format

For each test case, output the maximum possible length of a KK-beautiful subsequence of AA.

Constraints

  • 1T1001≤T≤100
  • 1N1031≤N≤103
  • 1K1031≤K≤103
  • 1Ai1031≤Ai≤103

Sample Input 1 

4
4 1
1 1 2 3
9 2
1 2 3 2 4 5 6 7 5
5 5
1 1 1 1 1
10 1
1 2 1 2 1 2 1 2 1 2

Sample Output 1 

3
5
5
6

Explanation

  • Test Case 1 : You can either choose [1,1,2][1,1,2] or [1,1,3][1,1,3] as a subsequence. Both of the subsequences are 11-beautiful. So the maximum length of a 11-beautiful subsequence is 33.

  • Test Case 2 : It is optimal to choose the subsequence [1,2,2,5,5][1,2,2,5,5]. So the maximum length of a 22-beautiful subsequence is 55.

  • Test Case 3 : You can choose the entire array as a subsequence because the given array is KK-beautiful for any K0K≥0, which includes K=5K=5.

Leave a Comment