SPECIALONE-Editorial

PROBLEM LINK:

Contest

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;
    }
}