Help in Birthday Blast| Runtime Terror 2

help
1

Link to problem statement (Hackerrank):

I’m getting the naive approach i.e I must keep blasting those m balloons which have maximum value at that instant. Clearly this is giving TLE in most of the cases so, if anyone can guide in optimizing it then please guide.

Here’s my attempt:

#include<bits/stdc++.h>
using namespace std;
#include<unordered_set>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define rep(a,b,c) for(int a=b;a<c;a++)
#define pb(v,a)    v.push_back(a);
#define INF 1000000009
#define MAX 100005
#define pi 3.14159265358979323846
int max(int a,int b){
    return (a>b?a:b);
}
int min(int a,int b){
    return (a<b?a:b);
}


//SOLVER
void solve(){
    int n,m;cin>>n>>m;
    multiset<ll> s;
    ll u;
    rep(i,0,n){
        cin>>u;
        s.insert(u);
    }
    bool t=1;ll res=0;
    do{
        int c=m;
        while(c){
            int x=*prev(s.end());
            if(x!=0){
            s.erase(prev(s.end()));
            s.insert(x-1);
            c--;}
            else{t=0;break;}
        }
    if(t)res++;
    }while(t);
cout<<res<<"\n";
}


//drive
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    //cin>>t;
    t=1;
    while(t--){
    solve();
    }
    return 0;
}
2

It looks like the question is a clone of this problem.

And surprisingly, the solution isn’t passing. Test cases should be wrong (or) the solution is wrong.

Edit: There was a mistake. The following solution is accepted. Test cases are fine.

CPP Code 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll number_of_teams(vector<ll>& teams_list, ll N, ll K)
{

    auto is_possible
        = [](vector<ll>& teams, ll N, ll T, ll k) {
              ll sum = 0;
              for (int i = 0; i < N; i++) {
                  sum += min(T, teams[i]);
              }
              return (sum >= (T * k));
          };

    ll lb = 0, ub = 10000000LL;

    while (lb <= ub) {
        ll mid = lb + (ub - lb) / 2;
        if (is_possible(teams_list, N, mid, K)) {
            if (!is_possible(teams_list, N, mid + 1, K)) {
                return mid;
            }
            else {
                lb = mid + 1;
            }
        }
        else {
            ub = mid - 1;
        }
    }
    return 0L;
}

void solve()
{
    ll N = 0, M = 0;
    cin >> N >> M;
    vector<ll> a(N);
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }
    cout << number_of_teams(a, N, M) << '\n';
}

int main() {
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}
1 Like
3

COOL!! Thanks a lot that helped!