COPS - Editorial

Sir, my approach is O(mlogm) ?
Here is my code code

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

Any idea why i am getting wrong answer ?
https://www.codechef.com/viewsolution/41551792
Thank you!

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])>2
cover:
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.

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

Unscrambled it - pay attention to compiler warnings - you might think that a[100] = {0} clears the array a, but that’s not what it does.

[simon@simon-laptop][08:14:14]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling nitishsharma12-COPS.cpp
+ g++ -std=c++14 nitishsharma12-COPS.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
nitishsharma12-COPS.cpp: In function ‘int main()’:
nitishsharma12-COPS.cpp:10:14: warning: array subscript is above array bounds [-Warray-bounds]
         a[100]={0};
         ~~~~~^
+ set +x
Successful
2 Likes

thanku sir

1 Like

Hii everyone , I tried to solve this COPS problem with an approach , and I was able to pass all the given sample test cases, but while submitting it , it was showing WRONG ANSWER. Can anyone help me to find out why this approach is giving wrong answer.

Link to the solution :
https://www.codechef.com/viewsolution/47712485

Consider the test input:

1
1 9 3
1
1 Like

Thank you very much . I got the mistake and now it is running correctly .

1 Like

CodeChef: Practical coding for everyone : link to my solution.
What changes should I make to my code for it to work?
Thanks.

Can someone please point out the problem with my code. Here is the link to my code:
https://www.codechef.com/viewsolution/49796754

I know it’s failing but I am unable to get where I have made the mistake.

Hello!

3
4 7 8
12 52 56 8
2 10 2
21 75
2 5 8
10 51
0
18
9
*** stack smashing detected ***: terminated
Aborted (core dumped)

Process returned 134 (0x86)   execution time : 1.402 s
Press ENTER to continue.

I am having above error in this question code goes here:-

#include <bits/stdc++.h>
using namespace std;

/*
[1,2,3,4,5,6,7]
1 2 3 4 5 6 7 */
/*
void color(int arr[],int start,int endd){
    for(int i = start-1;i<endd;++i)
    {
        arr[i]=1; // 1 means covered and not safe
    }
}*/

int main()
{
    long t;
    cin>>t;
    for(int k = 0;k<t;++k)
    {   int A[100] = {0};
        int M,x,y;
        cin>>M>>x>>y;
        int cpos=0;
        for(int i=0;i<M;++i)
        {
            cin>>cpos;
            int st = cpos-(x*y);
            if(st<1){
                st =1;
            }
            int en = cpos+(x*y);
            //color(A,st,en);
        for(int i = st-1;i<en;++i)
            {
                A[i]=1; // 1 means covered and not safe
            }
        }
        cout<<count(A,A+100,0)<<"\n";

    }

}

Explanation:- for possible ranges of cops made the corresponding locations = 1 and counted the positions where safe houses are present.

Solution Logic : 100% correct
Problem: STACK SMASHING ERROR ie runtime error SIGSEGV