HackerEarth Road to playoffs problem solution

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)

coding problems solutions