PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Tester: Felipe Mota
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
In front of a local shop, there are N spots, each adjacent pair of spots being at distance of 1 foot where each spot may be empty or not. Determine whether the people are following social distancing or not. Social distancing is not being followed if there are two people at a distance of less than 6 feet.
QUICK EXPLANATION
- In order for social distancing to be followed, for each non-empty spot, the previous 5 spots should be empty, which can be naively checked.
- Another solution would be to keep track of the previous non-empty spot. If the current spot is non-empty, the number of empty spots between previous and current spots must be at least 5.
EXPLANATION
Presenting two alternative solutions.
First solution
This problem just requires to manually check whether, for each pair of non-empty spots, there must be at least 5 empty spots in between.
So we can iterate from 1 to N, and if this spot is non-empty, let us check the previous 5 spots. If any of these 5 spots is non-empty, social distancing is not being followed. This solution takes 5*N iterations.
Second solution
Let us check the spots from left to right and keep track of the last non-empty spot. If the current spot is not empty, we compute the distance between the last non-empty spot and the current spot. If the distance is less than 6, Social distancing is not being followed. We also update the last non-empty spot to the current spot. This solution requires only N iterations.
TIME COMPLEXITY
The time complexity is O(N) per test case.
SOLUTIONS:
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
assert(1 <= t && t <= 100);
for(int _ = 0; _ < t; _++){
int n;
cin >> n;
assert(1 <= n && n <= 100);
vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
assert(a[i] == 0 || a[i] == 1);
}
int D = 10;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(a[i] && a[j])
D = min(D, abs(j - i));
cout << (D < 6 ? "NO\n" : "YES\n");
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class COVIDLQ{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
int[] a = new int[n];
for(int i = 0; i< n; i++)a[i] = ni();
int prevPos = -6;
boolean yes = true;
for(int i = 0; i< n; i++){
if(a[i] == 1){
if(i-prevPos < 6)yes = false;
prevPos = i;
}
}
pn(yes?"YES":"NO");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new COVIDLQ().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
Thanks.