Horse Race

Practice

4 (7 votes)

Algorithms

Binary search

Problem

57% Success 1058 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You own a race course where \(N\) different races are played on a day and the performance of the winner is recorded in an array \(A\). The winner of the \(i'th\) race is \(A[i]\) horse. Being the owner, you are only interested in the performance of all the horses numbered from \(1\) to \(M\). Let's denote the number of races won by the horses numbered from \(1\) to \(M\) by array \(B\), where \(B[j]\) denotes the number of races won by horse \(j\) (\(1 \leq j \leq M\)). Let \(K\) denote the minimum value among all the elements of the array \(B\). You are allowed to perform the following operations at most \(X\) times (maybe 0). Choose index \(i\) (\(1 <= i <= N\)) change the value of \(A[i]\) i.e. the winner of race \(i\). You are given an integer \(X\) denoting the maximum number of operations you can perform. Find the maximum possible value of \(K\) after performing atmost \(X\) operations. Note: There can be horses greater than \(M (M \leq N)\) participating in the race, but we only care about the horses numbered from \(1\) to \(M\). Input Format The first line contains an integer \(T\), which denotes the number of test cases. The first line of each test case contains three integers, denoting the value of \(N\), \(M\), and \(X\) respectively. The second line of each test case contains \(N\) space-separated integers, denoting the elements of array \(A\). Output Format For each test case, print the maximum possible value of \(K\). Constraints \(1 \leq T \leq 10\)\(1 \leq N, M, X \leq 10^5\)\(1 \leq M, A[i] \leq N\)

Sample Input

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

Sample Output

3
1
2

Explanation

For test case \(1\): Initially, the array \(B\) is \([2,4]\). Now, we can perform at most two operations, so if we change \(A[2]\) to \(1\). The array \(B\) will be \([3,4]\) and the minimum of array \(B\) i.e. \(K=3\). There is no way to increase the value of \(K\) by further operations. So, the answer will be \(3\). For test case \(2\): Here initially, the array \(B\) is \([2,0,1]\) and we can perform at most \(1\) operations on the array \(A\). So if we change \(A[4]=2\). The array \(B\) will be \([2,1,1]\) and the minimum of array \(B\) i.e. \(K=1\). So, the answer will be \(1\). For test case \(3\): Here initially, the array \(B\) is \([1,2]\) and we can perform at most \(2\) operations on the array \(A\). So if we change \(A[4]=1\). The array \(B\) will be \([2,2]\) and the minimum of array \(B\) i.e. \(K=2\). There is no way to increase the value of \(K\) by further operations. So, the answer will be \(2\).

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Results

Custom Input

Run your code to see the output

Submissions