COPS - Editorial

editorial
, , ,
42

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

43 
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
44

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
45

thanks bruh
it was a silly mistake

1 Like
46

can we pls help me , because this code is getting WA and i am able to figure out at which test cases its failing

47

This is not the link of your submission.

1 Like
48

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
49

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

1 Like
50

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

51

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

52

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

53

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

54

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

55

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

56

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

57

The log is base 2

1 Like
58

oh kk

59

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

No Idea Why I am getting wrong answer

60

Consider the test input:

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

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;

}

`