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