REDALERT - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Soumyadeep Pal
Tester : Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given the prediction of rain in the upcoming N days in the city. Initially, the water level of the city is zero millimeters. The amount of rain on the i^{th} day can be described by an array A as follows:

  • If A_i \gt 0, the water level of the city will increase by A_i millimeters.
  • If A_i = 0 , there will be no rain on the i^{th} day. The water level of the city decreases by D millimeters on such days. If the water level is less than D millimeters before the i^{th} day, then the water level will become zero.

There will be a red alert in the city if the water level exceeds H millimeters on any of the N days. Print YES if there will be a red alert, otherwise print NO.

EXPLANATION:

We just need to find the water level for each day and if any day water level exceeds H millimeters we call that a Red Alert. So our main focus is on finding the water level for all the days. How we can do that? Just do what the problem says.

Let’s maintain the current water level which initially, is 0 millimeters. We can go to the next day with the following two cases:

  • A_i \gt 0

\hspace{0.7cm} It means that there is rain in the i_{th} day and hence the current water level will rise by A_i millimeters. After that, we can check whether the current water level exceeds H millimeters or not.

  • A_i = 0

\hspace{0.7cm} Since there is no rain, hence the current water level will decrease by D millimeters. If after decreasing, the current water level becomes less than 0, we can simply make that 0.

And yes we are done !!

TIME COMPLEXITY:

O(N) per test case

SOLUTIONS:

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

void solve() {
	int n, d, h;
	cin >> n >> d >> h;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		if (i > 0) a[i] = a[i - 1];
		if (x > 0) {
			a[i] += x;
		} else {
			if (a[i] >= d) a[i] -= d;
			else a[i] = 0;
		}
	}
	if (*max_element(a.begin(), a.end()) > h) cout << "YES\n";
	else cout << "NO\n";
}

signed main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}
Tester

#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
    int n, d, h;
    cin >> n >> d >> h;
    int w = 0;
    bool ok = true;
    rep(i, 0, n) {
        int a;
        cin >> a;
        if(a == 0) w = max(0, w - d);
        else w += a;
        if(w > h) ok = false;
    }
    cout << (!ok ? "YES" : "NO") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n,d,h;
	cin>>n>>d>>h;

	bool ok = false;

	int lev = 0;

	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;

		if(x!=0)
			lev+=x;
		else
			lev = max(0,lev-d);

		if(lev>h)
			ok = true;
	}

	if(ok)
		cout<<"Yes"<<"\n";
	else
		cout<<"NO"<<"\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

CAN ANYBODY POINT OUT MY MISTAKE ??

#include
using namespace std;

int main() {
int t;
cin>>t;
int N,D,H;
int a;
for(int i=0;i<t;i++)
{
int wl =0;
cin>>N>>D>>H;
for(int j=0;j<N;j++)
{
cin>>a;
if(a>0)
wl+=a;
else
wl = (wl>D)?(wl-D):0;
if(wl>H)
{
cout<<“YES”<<endl;
break;
}
else if(j==(N-1))
{
cout<<“NO”<<endl;
}
}
}
return 0;
}

You stopped taking input as soon as you found Red Alert and that brings Red Alert for your submission.

1 Like

Found the mistake. Thank you for your quick response!!!

whats the problem in this solution??

#include
using namespace std;

int main() {
// your code goes here
int t,n,d,h;
cin>>t;
while(t–){
int sum=0;
cin>>n>>d>>h;
int arr[n];
for(int i=0; i<n; i++){
cin>>arr[i];
}
for(int i=0; i<n; i++){
if(arr[i]!=0){
sum+=arr[i];
}
else{
sum-=d;
}
}
if(sum<=h)
cout<<“NO”<<endl;
else{
cout<<“YES”<<endl;
}
}
return 0;
}

  1. you are not checking the condition when sum<d and if sum<d then directly u need to make sum as zero
  2. the value of sum can be greater than H even before iterating the entire loop so even if on one day the value of SUM>H then red alert is possible so it is advisable to break the loop whenever u find sum>H and then print accordingly and for this create a flag variable and intialize it to zero and if Sum>H make the flag as 1 and break the loop and now outside for loop print yes or no accordingly by keeping a if condition by checking if your flag is 1 print yes else print NO

I hope this explanation helps you !!!

CAN SOMEONE POINT MY MISTAKE
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main() {long long t;cin>>t;while(t–){ll n,d,h,a,s=0;cin>>n>>d>>h;
for(ll i=0;i<n;i++){
cin>>a; s+=a;if(a==0) s-=d;if(s<0) s=0;
if(s>h){ cout<<“YES”<<"\n";break;}
} if(h>=s) cout<<“NO”<<"\n";

}
// your code goes here
return 0;
}

CAN ANYBODY POINT OUT MY MISTAKE ??
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here

int t;
cin>>t;
while(t--){
    long long N,D,H;
    cin>>N>>D>>H;
    long long arr[N];
    long long prefix[N];
    for(int i=0;i<N;i++){
        cin>>arr[i];
        if(arr[i]==0){
            arr[i]=-D;
        }
    }
   
   
    prefix[0]=arr[0];
    for(int i=1;i<=N;i++){
        prefix[i]=prefix[i-1]+arr[i];
    }
    long long max=*max_element(prefix,prefix+N);
   
    if(max>H){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
    
}
return 0;

}

Out of bounds access on sample test input:

[simon@simon-laptop][18:56:26]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling sudhanshu_290-REDALERT.cpp
+ g++ -std=c++14 sudhanshu_290-REDALERT.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv -fno-sanitize-recover
+ set +x
Successful
[simon@simon-laptop][18:56:30]
[~/devel/hackerrank/otherpeoples]>echo "4
4 2 6
1 3 0 2
2 1 100
1 100
4 2 3
1 2 0 2
3 7 10
5 3 9 
" | ./a.out
sudhanshu_290-REDALERT.cpp:24:40: runtime error: index 4 out of bounds for type 'long long int [*]'

can you please find the error in my code ??
https://www.codechef.com/viewsolution/49327418

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

int main() {
int t,d,h,n,w,flag;
scanf("%d",&t);
for(int i=0;i<t;i++){
scanf("%d %d %d",&n,&d,&h);
int a[n];
w=0;
flag=0;
for(int i=0;i<n;i++){
scanf("%d ",&a[i]);
if(a[i]>0)w=w+a[i];
if(a[i]==0) {
if(w>=d)w=w-d;
else if(w<d) w=0;
}

        if(w>h){
             flag++;
             }
    }
 
  if(flag==0)printf("N0\n");
  else  printf("YES\n");
}
return 0;

}

You’re printing out N0 instead of NO :slight_smile:

Array indexing for prefix array is wrong, use N+1

You should not break while taking the input if you find s>h… all inputs of test case are not taken till then

for every day , you have to check whether there is red alert or not . but you are checking at last which is wrong

Can someone say why this code is not working

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int redalert(int arr[],int n,int d,int h,int rain)

{

for(int i=0;i<n;i++){

    if(arr[i] > 0){

        rain = rain+arr[i];

    }

    if(arr[i] == 0){

        if(rain < d){

            rain=0;

        }

    else{

            rain = rain-d;

        }

    }

    if(rain > h){

        return 1;

    }

}  

}

int main()

{

ll t;

cin>>t;

while(t--){

int n,d,h,rain=0;

cin>>n>>d>>h;

int arr[n];

for(int i=0;i<n;i++)

{

    cin>>arr[i];

}

int flag = redalert(arr,n,d,h,rain);

if(flag == 1){

    cout<<"YES"<<"\n";

}

else{

    cout<<"NO"<<"\n";

}

}

}

Fix this compiler warning and ask again :slight_smile:

[simon@simon-laptop][08:55:07]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling sarvesh_1361-REDALERT.cpp
+ g++ -std=c++14 sarvesh_1361-REDALERT.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv -fno-sanitize-recover
sarvesh_1361-REDALERT.cpp: In function ‘int redalert(int*, int, int, int, int)’:
sarvesh_1361-REDALERT.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
+ set +x
Successful

T=int(input())
for i in range(T):
r=list(map(int,input().split()))
a=list(map(int,input().split()))
s=0
Z=0
for j in range(len(a)):
if a[j]>0:
s=s+a[j]
if s>r[2]:
print(“YES”)
Z=Z+1
break
if a[j]==0:
if a[j-1]<r[1]:
s=0
else:
s=s-r[1]
if Z==0:
print(“NO”)
can you please find my mistake??

whats the problem with this code??

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t!=0)
{
int n,d,h;
cin>>n>>d>>h;
int a[n];
int sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>0)
{
sum+=a[i];
}
else
{
if(sum<d)
{
sum=0;
}
else
{
sum=sum-d;
}
}
if(sum>h)
{
cout<<“YES”<<endl;
break;
}
}
if(sum<=h)
{
cout<<“NO”<<endl;
}
t–;

}
return 0;

}