Thanks. It worked for me.
Hey i dont know why am i getting a wrong answer. Can somebody please help?
https://www.codechef.com/viewsolution/28366715
Here’s a random testcase your solution fails on:
5
10 7 8
20 9 13 10 42 52 43 67 100 74
8 4 1
33 49 27 78 48 30 82 43
3 10 4
12 54 26
2 1 5
7 92
4 3 1
7 1 23 63
Edit:
He solved it.
here, I have applied range update query algorithm. it takes O(100) time complexity.
int a[105]={0};
int m,x,y;
cin>>m>>x>>y;
int i,b;
int s=x*y;
for(i=0; i<m; i++)
{
cin>>b;
int l=max(1,b-s);
int r=min(100+1,b+s+1);
a[l]+=1;
a[r]+=-1;
}
for(i=2; i<=100; i++)
{
a[i]=a[i]+a[i-1];
}
int cnt=0;
for(i=1; i<=100; i++)
{
if(a[i]==0)
cnt++;
}
cout<<cnt<<"\n";
for _ in range(int(input())):
m,x,y = map(int,input().split())
M = list(map(int,input().split()))
s = [1]100
t = xy
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)
hey ssjgz can u help me on this one i cant find why i am getting wa
Please either format your code or link to your submission - the forum software has mangled it and it won’t compile!
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)
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
)
thanks bruh
it was a silly mistake
can we pls help me , because this code is getting WA and i am able to figure out at which test cases its failing
This is not the link of your submission.
As @aryan12 points out, that is not the link to your submission: this is, though
Consider the testcase:
1
1 9 3
1
sorry for giving wrong link , BTW i sloved it and thanku for pointing out the error
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?