Road to playoffs

Practice

3 (6 votes)

Binary search

Algorithms

Greedy algorithms

Problem

83% Success 1188 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

In a football championship, N teams are competing against each other on the league stage. The current number of points of each team are X1, X2, X3....XN. M days of league stage are remaining and on each day K teams win and each of the winning team's points is incremented by 1. Top B teams will qualify for the playoffs in the championship. Officials of the tournament want to how many teams have a non-zero probability of making it to the playoffs. Note: If points of certain teams are equal, any of the teams can qualify for playoffs and each team has equal probability. Input format The first line contains an integer T denoting the number of test cases. For each test case: The first line contains four space-separated integers N, M, K, and B. The second line contains N space-separated integers X1, X2, X3...XN. Output format Print T integers. For each test case: Print the number of teams that have a non-zero probability of making it to the playoffs. Constraints \( 1\leq T \leq 20000\) \(1 \leq N \leq 200000\) \(1 \leq M \leq 10^9\) \(1 \leq B,K < N\) \( 1 \leq X_i \leq 10^9\) Sum of N over all test cases will not exceed 200000.

Sample Input

Sample Output

3
4

Explanation

First test case: Only one team can make it to the playoffs, two days of league stage are left and 2 points on each day are to be gained. Every team has probablity to qualify for playoffs other than team with 1 point. Let us look at the scenarios: Bold are those teams which we want to win: Team with 4 points: [4, 1,2,3] -> [5, 2,2,3] -> [5,3,2,3] Team with 1 points has no chance to qualify ( Zero probablity) Team with 2 points: [4, 1, 2,3] -> [4, 2, 3,3] -> [4,3,4,3] (Any of the first or third team can qualify so probablity>0) Team with 3 points: [4, 1,2, 3] -> [4, 2,2, 4] -> [4,3,2,5] 4th team has maximum points so they can be choosen in this case. So all teams other than second have non-zero chance and also note that in case of ties you can qualify any team you want.

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor