In this

**HackerEarth Road to playoffs problem solution**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.

## HackerEarth Road to playoffs problem solution.

`#include<bits/stdc++.h>`

using namespace std;

#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define mod 1000000007

#define endl "\n"

#define test ll t; cin>>t; while(t--)

typedef long long int ll;

bool check(vector<ll>&a,ll mid,ll n,ll m,ll k,ll p){

ll total=0;

for(ll i=0;i<n;i++){

if(i+1<p || i>=mid){

total+=m;

}

else{

if(a[i]>a[mid]+m){

return false;

}

total+=(a[mid]+m-a[i]);

}

}

return (total>=m*k);

}

int main() {

FIO;

test

{

ll n,m,k,b; cin>>n>>m>>k>>b;

vector<ll>a(n);

for(auto &it:a) cin>>it;

sort(a.begin(),a.end(),greater<ll>());

ll ans=b,st=b,dr=n-1;

while(st<=dr){

ll mid=(st+dr)/2;

if(check(a,mid,n,m,k,b)){

ans=mid+1;

st=mid+1;

}

else{

dr=mid-1;

}

}

cout<<ans<<endl;

}

return 0;

}

### Second solution

`from math import inf`

t = int(input())

while t > 0:

t -= 1

n, m, k, b = map(int, input().split())

a = list(map(int, input().split()))

a.sort(reverse=True)

lo = b - 1

hi = n

while hi - lo > 1:

i = (lo + hi) // 2

need = m * (k - (b - 1) - (n - i))

for j in range(b - 1, i):

if a[j] > a[i] + m:

need = inf

else:

need -= a[i] + m - a[j]

if need > 0:

hi = i

else:

lo = i

print(lo + 1)

## 0 Comments