 COVIDLQ - Editorial

Tester: Felipe Mota
Editorialist: Taranpreet Singh

Cakewalk

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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}

Feel free to share your approach. Suggestions are welcomed as always. 2 Likes

What is wrong in following code (C++) ?
https://www.codechef.com/viewsolution/31038524

The python code equivalent to above code is being accepted
https://www.codechef.com/viewsolution/31050386

1 Like

Detailed solution can be seen here.

Initially I tried this but I got WA.
https://www.codechef.com/viewsolution/31334347
Can anybody help me what is the wrong with the code?

@prmondal
Here is a test case for your reference.
3
4
1 0 1 1
5
1 1 1 1 1
5
1 1 1 1 1

The breaking of loop is causing the error in your code. Because whenever you decide that it is not possible, you stop reading the “a” array, so the next a[i] of the current test case, get read as n of the next test case.

3 Likes

I was totally lost. Thanks.

Both of your solutions are different. In the python code you are first storing all the values in a list but in C++ code you are taking a value and then checking the condition so when the condition fails it exits the for loop and then the next value will not be taken up as A it will be stored in n.

Test case:
3
3
1 1 1
2
1 1
3
1 1 1

NO
YES
YES

Correct output:
NO
NO
NO

@vinayak_mohite

2 Likes

@sudheerays123
There is no need of using long long int as the constraints are N<100

I am getting SIGSEGV error in this solution. Pls do help I am a beginner.

https://www.codechef.com/viewsolution/31856205

Hey @codechef2057 ,

The reason why you are getting SIGSEGV is because you have declared vector ‘people’ and you have not declared size and you are doing cin >> people[i];

So , change from vector people; to vector people(105);

1 Like

Got it…!
Thanks!

What is wrong in my code please anyone explain.
#include<bits/stdc++.h>
using namespace std;
int count(int arr[],int l,int h)
{
int res=0;
for(int i=l;i<h;i++)
{
if(arr[i]==1)
res++;
}
return res;
}
int check(int arr[],int n)
{
int res=0,m,k;
for(int i=0;i<n;i++)
{
if(arr[i]==1){
m=i+6;
k=i+1;
m=(m<=n)?m:n;
k=(k<n)?k:n;
res=count(arr,k,m);
if(res==0)
return 0;
else
return 1;
}
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
if(t>=1 && t<=1000)
{
while(t–)
{
int n,temp,flag=0,c;
cin>>n;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
if(n%6==0)
temp=n/6;
else
temp=(n/6)+1;
c=count(arr,0,n);
if(c<=temp)
{
flag=check(arr,n);
}
else
flag=1;
if(flag==0)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}

}
return 0;

}

It didn’t worked. Still getting the error.

i modified my program (initially was using vectors) .My logic seems to fine. It works with multiple test cases in my IDE. However I am getting wrong answer. Please do look into it. Thanks a lot in advance.

#include<iostream>

using namespace std;

int main()
{
int t,size,i,num,prev,dis,flag;
cin >> t;
while(t--)
{
prev=-1;
flag=0;
cin >> size;
for(i=0;i<size;i++)
{
cin >> num;
if(num==1 && prev==-1)
{
prev=i;
}
else if(num==1 && prev!=-1)
{
dis=i-prev;
if(dis<6)
{
flag=1;

}
prev=i;

}

}
if(flag==1)
cout << "NO" << endl;
else
{
cout << "YES" << endl;
}

}

return 0;

}

My commented code for the solution.

I tested with the test cases from editorial as well and it worked but my code didn’t get accepted.

using namespace std;
#define endl ‘\n’;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int ar[n];
int flag=0;
for(int i=0;i<n;i++)
{
cin>>ar[i];
}
for(int i=0;i<n;i++)
{
int b;
int c=0;
if(ar[i]==1 )
{
b=i;

if(i+5<=n)
{

for(int j=b+1;j<b+6;j++)
{

if(ar[j]==0)
{
c++;

}
}
if(c==5)
{
flag=1;
}
else{
flag=0;
}
}
else{

for(int j=b+1;j<n;j++)
{

if(ar[j]==1)
{
flag=0;
break;
}
}

}

}
}

if(flag==1)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}

}

return 0;

}

#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n,i,index=-6;
bool flag=true;
cin>>n;
int a[n];
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
if(a[i]){
if(i-index<6){
flag=false;
break;
}
else{
index=i;
}
}
}
if(flag) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}

/* WHEN I SUBMIT IT SHOWS ME WRONG ANS EVEN AFTER IT GIVING ME ALL RUIGHT ANS … PLEASE HELP ME I AM NEW HERE ( I AM COPY THIS HERE FROM MY IDE */

int test,ncircle;

Scanner sc=new Scanner(System.in);

test=sc.nextInt();

String[] ans=new String[test];

int c=0;

while(test!=0)

{

test--;

ncircle=sc.nextInt();

int[] series=new int[ncircle];

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

{

series[i]=sc.nextInt();

}

for(int i=0;i<series.length;i++)

{

if(series[i]==1)

{

if(i+5<series.length)

{

for(int j=i+1;j<=i+5;j++)

{

if(series[j]==1)

{

ans[c]="NO";

break;

}

else

{

ans[c]="YES";

}

}

}

else

{

for(int j=i+1;j<series.length;j++)

{

if(series[j]==1)

{

ans[c]="NO";

break;

}

else

ans[c]="YES";

}

}

}

}

c++;

}

for(int ii=0;ii<ans.length;ii++)

{

System.out.println(ans[ii]);

}

What is wrong with my code . It is giving wrong ans.
https://www.codechef.com/viewsolution/31897538