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;
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)
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