NODRUGS - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

Setter: Arshdeep Singh
Tester: Vichitr Gandas, Anshu Garg

DIFFICULTY:

SIMPLE

PROBLEM:

Given an array S of size N, determine if it is possible to add integer K (may be negative) to S_N at most L-1 times, such that S_N is then greater than all other elements in S.

EXPLANATION:

If K \lt 0, injecting the drug will reduce his speed; so it’s better to not inject the drug at all. In this case, your friend wins only if he is faster than everyone else \implies S_N > S_i should hold for all valid i < N.

If K > 0, we can repeatedly inject the drug until the limit is reached (that is, we can inject the drug L-1 times), increasing his speed in each dose. If after this, your friend is faster than everyone else, he wins \implies S_N+K*(L-1) > S_i should hold for all valid i < N.

TIME COMPLEXITY:

Since we iterate over array S once to determine the answer, the time complexity for each test case is:

O(N)

SOLUTIONS:

Editorialist’s solution can be found here


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll t;
cin>>t;
while(t–){
int n,k,limit,mx=INT_MIN,friend_speed;
cin>>n>>k>>limit;
if(n==1){
cout<<“YES”<<endl;
continue;
}
vector v(n);
for(int i=0;i<n-1;i++){
cin>>v[i];
mx=max(mx,v[i]);
}
cin>>friend_speed;
if(k>=0){
friend_speed=friend_speed+k*(limit-1);
}
if(friend_speed>mx){
cout<<“YES”<<endl;
}
else{
cout<<“NO”<<endl;
}
}
return 0;
}

Can anyone tell me why it is showing runtime error?

Some of the mistakes are:
1.while(t-) is wrong. One should use while(t–)
2.Declaration and Implementation of vector is wrong
3. YES should be used inside same type of apostrophe like “YES”.

Happy Coding bro!

Sigh - and this is why you should please either format your code or (better!) link to your submission :slight_smile:

Anyway, you’ve solved it now so you presumably figured out the answer. For anyone wondering: in the N=1 case, the speeds aren’t read in, so that hang around in stdin corrupting subsequent testcases.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k,l;
        cin>>n>>k>>l;
        int a[n];
        int max = INT_MIN;
        for(int i = 0;i<n;i++){
            cin>>a[i];
            if(i<(n-1) && max<a[i])
                max = a[i];
        }
        int units = max - a[n-1];
        if(n == 1)
            cout<<"Yes\n";
        else if(k<=0)
            cout<<"No\n";
        else{
            units = units/k;
            units++;
            if(units<l)
                cout<<"Yes\n";
            else 
                cout<<"No\n";
        }
    }
    return 0;
}