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


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)