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