COPS - Editorial

Thanks. It worked for me.

1 Like

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.

1 Like

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";
1 Like

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)

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! :slight_smile:

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)
1 Like

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)

1 Like

thanks bruh
it was a silly mistake

1 Like

https://www.codechef.com/submit/COPS
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.

1 Like

As @aryan12 points out, that is not the link to your submission: this is, though :slight_smile:

Consider the testcase:

1
1 9 3
1

sorry for giving wrong link , BTW i sloved it and thanku for pointing out the error

1 Like

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?