Equal Diverse Teams

2.9

14 votes
Greedy algorithm, Linear Search, , Algorithms
Problem

 Alice has N students in his class, numbered 1 through N. The ith student has expertise in a subject numbered Ai.

Alice has to divide the students into two teams. The uniqueness of a team is defined as the number of distinct subjects such that there is atleast one student in the team with expertise in the subject. For example, the uniqueness of a team denoted by A=[1,3,1,4,4] is 3.

Alice wants to distribute the students of the class into two teams such that each student belongs to exactly one team and the uniqueness of each team is exactly K. Will he be able to do so?

Input format

  • The first line of input contains an integer T denoting the number of test cases. The description of each test case is as follows:
  • The first line of each test case contains two integers N and K.
  • The second line of each test case contains N integers A1,A2,,AN.

Output format

For each test case, print YES if Alice is able to make two teams satisfying the given conditions, otherwise print NO.

Constraints

1T1052N1051KN1AiNSum of N over all test cases does not exceed 3105.

Sample Input
2
6 2
1 4 4 6 2 1
4 2
1 1 1 1
Sample Output
YES
NO
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  •  In the first test case, Alice can put the fourth and fifth student in the first team and the remaining students in the second team making the expertises of the teams look as [2,6],[1,1,4,4]. Here both team has a uniqueness of 2.
  • In the second test case, it is impossible to partition the students into two teams with uniqueness equal to 2.

 

 

Editor Image

?