COPS - Editorial

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;

}

`

We can also use difference array .
Time Complexity = O(100)

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

for sample input it is showing correct o/p .but WA when submitted

t=int(input())
for j in range(t):
    ar=[]
    count=0
    flag=True
    m,x,y=map(int,input().split())
    ar=list(map(int,input().split()))
    i=0
    while i<m-1:
        if ar[i]+x*y>=ar[i+1] or ar[i]+x*y>=100:
            if ar[i]+x*y>=100:
                break
        else:
            if ar[i+1]-x*y>ar[i]+x*y:
                count+=ar[i+1]-ar[i]-2*x*y-1
        i=i+1
    if 100>ar[i]+x*y:
        count+=100-ar[i]-x*y
    if m==1:
        print(100-min(100,ar[0]+x*y)+max(0,ar[0]-x*y))
    else:
        print(count)

Here’s a random test input your solution fails on:

1
3 4 3
28 32 73
2 Likes

Yes mistake is I haven’t consider the lower bound of the first cop. Thank u

1 Like

Sir, please provide answer also. Thanks

46
1 Like

Thanks Sir.

1 Like

Sir, my approach is O(mlogm) ?
Here is my code code

I was able to complete this in O(N) complexity where N is the number of cops.

Logic:
1> select all the houses where thief cannot go ie for every cop position…lower_house=i-xy and upper_house=i+x*y where i is current position of cop, x is speed of that cop and y is time for which he can search…which is given in question…both lower_house and upper_house are included.
2> create a set (python) of these values(lower_house to upper_house) for example set([i for i in range(lower_house,upper_house+1,1])…note if value of lower_house is lesser than 1 update its value to 1 and if value of upper_house exceeds 100 then update the value to 100…because the houses are numbered from 1 to 100 both inclusive, we cannot exceed these bounds.
3> take union of all such houses which are generated at every iteration of step 1 and 2 combined for each cop…union because even if the same house is visited by other cops it would be counted only once in every step.
4> finally we would get a set of all the houses where the thief cannot go.
5>number of safe houses = 100 - len(set of the house which cops can visit).
solutionlink

1 Like

Can anyone please help me out in finding error in my code . It is passing sample test cases but gives wrong answer on submission.

here is my solution https://www.codechef.com/viewsolution/38667899

Any idea why i am getting wrong answer ?
https://www.codechef.com/viewsolution/41551792
Thank you!

the test cases given below,my code passed all but still its giving WA
T =int(input())
for _ in range(T):
count=0
M,X,Y=map(int,input().split())
list1=list(map(int,input().split()[:M]))
list1.sort()
cover=XY
for i in range(1,M,1):
if abs(list1[i]-list1[i-1])>2
cover:
count=count+abs(list1[i]-list1[i-1])-2*cover-1
if (list1[0]-1)>cover:
count=count+list1[0]-1-cover
if (100 - list1[-1]-1)>cover:
count=count+100-list1[-1]-cover
print(count)

great!

@ souravobl I don’t see your submission to this problem under your CodeChef profile and it’s really difficult to guess what indentation you have used when you don’t use preformatted text. Button: </>

T =int(input())
for _ in range(T):
    count=0

etc

how did u come up with this?

solutionn link not found

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,m,x,y,k,a[100],count1=0;
cin>>t;
while(t!=0)
{
cin>>m>>x>>y;
a[100]={0};
while(m!=0)
{
int l=x*y;
cin>>k;
if(l>=k)
{
for(int j=1;j<=k+l;j++)
{
if(a[j]!=-1)
a[j]=-1;
}
}
else
{
for(int j=k-l;j<=k+l;j++)
{
if(a[j]!=-1)
a[j]=-1;
}
}
m–;
}
for(int i=1;i<=100;i++)
{
if(a[i]!=-1)
count1++;
}
cout<<count1<<endl;
t–;
}
return 0;
}
please help me finding error in my code i am getting right anwer for each testcase separately but giving wrong answer when i am taking all the inputs together.