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)
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
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 CodeChef: Practical coding for everyone
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])>2cover:
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.