PROBLEM LINK:
Setter: priyansh2802
Tester: priyansh2802
Editorialist: priyansh2802
DIFFICULTY:
Simple
PREREQUISITES:
Basic observations
PROBLEM:
Rishika loves the number 2020, she tries to find 2020 in each and every sequence she is given but unfortunately, she is now tired of looking at all these sequences, your job is to code a program that outputs “YES” if a contiguous subsequence can be removed from the sequence and 2020 can be made or “NO” if it’s not possible
NOTE: -the array is an 0-based indexed array
EXPLANATION
If we try to code the most efficient code there are 5 cases possible:-
- The array looks like this :- 2 0 2 0 Contiguousblockofelements
- The array looks like this :- Contiguousblockofelements 2 0 2 0
- the array looks something like this 2 Contiguousblockofelements 0 2 0
- the array looks something like this 2 0 Contiguousblockofelements 2 0
- the array looks something like this 2 0 2 Contiguousblockofelements 0
Therefore,
- For the first test case we just needed to compare the first 4 elements to the 2 0 2 0
- For the second test case we just needed to check the last 4 elements of the array with 2 0 2 0
- For the third test case we just needed to check the first and the last three elements of the array and compare those elements with 2 0 2 0
- For the fourth test case we just needed to check the first two and the last two elements of the array and compare those elements with 2 0 2 0
- For the fifth test case we just needed to check the first three and the last one elements of the array and compare those elements with 2 0 2 0.
If any of these cases are true the output should be YES else NO
TIME COMPLEXITY
Time complexity is O(1) if only if-else statements are used
SOLUTIONS:
Setter's Solution
C++
#include<iostream>
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int32_t main(void)
{
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
// 2 #contigous block# 0 2 0
if(arr[0]==2 && arr[arr.size()-3]==0 && arr[arr.size()-2]==2 && arr[arr.size()-1]==0)
{
cout<<"YES"<<endl;
}
//2 0 #contigous block# 2 0
else if(arr[0]==2 && arr[1]==0 && arr[arr.size()-2]==2 && arr[arr.size()-1]==0)
{
cout<<"YES"<<endl;
}
// 2 0 2 #contigous block# 0
else if(arr[0]==2 && arr[1]==0 && arr[2]==2 && arr[arr.size()-1]==0)
{
cout<<"YES"<<endl;
}
else if(arr[0]==2 && arr[1]==0 && arr[2]==2 && arr[3]==0)
{
cout<<"YES"<<endl;
}
else if(arr[arr.size()-4]==2 && arr[arr.size()-3]==0 && arr[arr.size()-2]==2 && arr[arr.size()-1]==0)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}