COPS - Editorial

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

for _ in range(int(input())):
    m,x,y = map(int,input().split())
    M = list(map(int,input().split()))
    s = [1]*100
    t = x*y
    for i in range(m):
        min = M[i]-t
        if(min<0):
            min=1
        max = M[i]+t
        if(max>100):
            max = 100
        for j in range(min-1,max):
            if(s[j]==1):
                s[j]=0
    t = 0
    for k in range(0,100):
        if(s[k]==1):
            t+=1
    print(t)
1 Like

Thanks - here’s a random testcase your solution fails on:

1
9 4 4
56 55 66 50 81 20 16 30 36 

(the answer should be 3)

1 Like

thanks bruh
it was a silly mistake

1 Like

https://www.codechef.com/submit/COPS
can we pls help me , because this code is getting WA and i am able to figure out at which test cases its failing

This is not the link of your submission.

1 Like

As @aryan12 points out, that is not the link to your submission: this is, though :slight_smile:

Consider the testcase:

1
1 9 3
1

sorry for giving wrong link , BTW i sloved it and thanku for pointing out the error

1 Like

Best solution I have seen so far for this problem. Time and space compl. both O(100)!!

Test case matches but still on submission i get wrong answer:

import java.util.*;

class code {
public static void main (String[] args) {
Scanner in=new Scanner(System.in);
int t,m,x,y,i,c,l,l1;
for (t=in.nextInt();t>0 ;t-- )
{
c=0;
m=in.nextInt();
x=in.nextInt()*in.nextInt();
int a[]=new int[m];
for(i=0;i<m;i++)
a[i]=in.nextInt();
if((a[0]-x-1)>0)
c=a[0]-x-1;
for(i=1;i<m;i++)
{
l=a[i]-x-1;
l1=a[i-1]+x;
if(l1>=100)
break;
if(l>0&&l>l1)
c=c+l-l1;
}
l=a[i-1]+x;
if(l<100)
c=c+(100-l);
System.out.println©;
}
}
}

My code isnt working despite correct logic. Pls help.
https://www.codechef.com/viewsolution/30976957

My code is executing successfully but the status says wrong answer.Please help what I am missing??
My code link

won’t O(HlogN) be lesser time complexity than O(H+N)

Actually no.
Consider this logN can be at max 6.64 (N = 100).
Max(H + N) =200
Max(HlogN) = 664

At N = 100, won’t Log N would be 2?

The log is base 2

1 Like

oh kk

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

No Idea Why I am getting wrong answer

Consider the test input:

1
8 3 1
41 80 64 2 47 89 5 69
1 Like

I think we can also do this
initialise a boolean array " bool mark[101] " to true intially
iterate over all the cop houses and mark the range of each cop to false
Now iterate over the whole array and check the houses that are safe marked to true.`#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

int t;
cin >> t;
bool mark[101];
for(int i = 1;i<=100;i++)mark[i] = true;
while(t--){
	
	int m,x,y;
	cin >> m >> x >> y;
	int cop[m];
	for(int i = 1;i<=m;i++)cin >> cop[i];
	int range = x*y;
	for(int i = 1;i<=m;i++){
		int copH = cop[i];
		int lim = copH+range;
                    //mark false for right range
		for(int j = copH;j <= lim && j<=100;j++)mark[j] = false;
		lim = copH - range;
                    //mark false for right range
		for(int j = copH;j >= lim && j>=1;j--)mark[j] = false;
	}	
	int cnt = 0;
	for(int i = 1;i<=100;i++){
                    //count the safe houses
		if(mark[i])cnt++;
		else mark[i] = true;
	}
	cout << cnt << "\n";

}



return 0;

}

`