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 < 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.