×

COPS - Editorial

Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey

Cakewalk

None

PROBLEM:

There are 100 houses in a lane, numbered from 1 to 100. N cops are positioned in some houses. A cop's running speed is $h$ houses per second and he can run for at max $t$ secs. Find number of houses where a thief can hide such that he won't be caught by any of the cops.

QUICK EXPLANATION:

For each house and each cop, we can check whether the cop can reach the house or not by checking whether distance between them is less than or equal to maximum distance a cop can travel ($h * t$). If some cop can reach a house, then the house is unsafe otherwise it is safe.

The editorial explains three methods of finding number of safe houses having time complexities of $\mathcal{O}(H N)$, $\mathcal{O}(H \, log N)$ and $\mathcal{O}(H + N)$ respectively, where $H$ denotes number of houses (is fixed to 100 in our problem) and $N$ denotes the number of cops.

Explanation

For a particular house, we want to find out whether this house can be checked by some cop or not. We know that a cop can cover a maximum of $h * t$ inter-house distances in $t$ secs. So, if the distance between the thief's hiding house and cop's house is less than or equal to $h * t$, then the cop can catch the thief. We just need to check whether the current house can be reached by any of the cops or not. If yes, then it is not safe otherwise it is safe.

So, we can describe the solution succinctly as follows.

ans = 0
for each house from 1 to 100:
safe = true
for each cop houses from 1 to N:
if (the cop can reach the house)
safe = false
if (safe) ans += 1


Clearly the above implementation of the problem will take $\mathcal{O}(100 * N)$ time.

Faster Solution

Let us say thief is currently at house $p$ and we want to check whether he will be safe in this house or not. If we can find the nearest cops in both directions of the lane from current house, then we just need to check whether these nearest cops in either direction can reach the house $p$ in time or not.

We will describe a method for finding nearest cop in forward direction faster than $\mathcal{O}(N)$ time. Backward direction can be handled similarly.

Let us can create a sorted array of houses of cops. We want to find the first element in the array having value $\geq p$. This can be done by using binary search over the array. Time complexity of this will be $\mathcal{O}(N)$ per search operation in array.

You can also find the same thing using $\mathtt{lower}$_$\mathtt{bound}$ in set in C++. set maintain a balanced binary search tree underneath it, which takes $\mathcal{O}(log N)$ time for each $\mathtt{lower}$_$\mathtt{bound}$ query.

So, this solution runs in $\mathcal{O}(100 * log N)$ time. Can we make it faster?

Even Faster Solution

We have to find $nextCopHouse$/$prevCopHouse$ information for each house faster. Let us see how can find $nextCopHouse$ information faster. Let us make a boolean array $isCop$ of size $100$ where $isCop[i]$ denotes that there is a cop in $i$-th house or not.

Now, we go from house number 100 to 1 and update the $nextCopHouse$ information by maintaining the position of latest house having cop in it.

latestHouseHavingCop = -1;
for house p from 100 to 1:
if (there is a cop in the house):
latestHouseHavingCop = p;
nextCopHouse[p] = latestHouseHavingCop;


Time complexity of this solution is $\mathcal{O}(N + 100)$.

AUTHOR'S, TESTER'S SOLUTIONS:

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

19.8k350498541

 1 Why am I getting wrong answer?Here is the link https://www.codechef.com/viewsolution/10048264 answered 11 May '16, 01:20 11●1 accept rate: 0%
 1 where to ask questions? answered 21 Mar '17, 17:50 120●6 accept rate: 10% If problem related then here , Else than on discuss (17 Sep '18, 19:24)
 0 i am unable to understand why i am getting wa. need help here is link to my soln: https://www.codechef.com/viewsolution/7510253 I got ac by changing cin to scanf and cout to printf..Can any one explain why such things happen? answered 20 Jul '15, 00:14 1 accept rate: 0%
 0 i tried to do it in O(m). Why is this worng? https://www.codechef.com/viewsolution/7506909 answered 20 Jul '15, 00:17 11●1 accept rate: 0%
 0 @sidharth14163 just check for a case 1 1 2 1 100 your first condition of breaking the loop is wrong . hope it would be clear :) answered 20 Jul '15, 00:32 4★mega 2 accept rate: 0%
 0 Did this with hashing :) This loop takes care of all possible boundary conditions. for(i=0 to m) { input val: for(j = max(val-x*y,0) ;j<=min(val+x*y,100);j++) arr[j]++; }  Now just check how many entries of arr are 0. answered 20 Jul '15, 01:52 291●2●3●20 accept rate: 10%
 0 test_cases = gets.to_i test_cases.times do m, x, y = gets.strip.split(" ").collect(&:to_i) prod = x * y all_houses = (1..100).to_a cops_houses = gets.strip.split(" ").collect(&:to_i) searchable_houses = [] cops_houses.each do |el| searchable_houses += ((el - prod)..el).to_a + (el..(el + prod)).to_a end safe_houses = all_houses - searchable_houses puts safe_houses.length end answered 27 Aug '16, 15:05 1 accept rate: 0%
 0 My code isnt working despite correct logic. Pls help. https://www.codechef.com/viewsolution/13138859 answered 21 Mar '17, 17:46 1 accept rate: 0%
 0 I just made a boolean array with 100 elements. For each cop position I checked +-20 positions and then counted how many false positions there were. I'm pretty sure it's a better solution since you don't have to check every house. answered 13 Jul '17, 00:40 0★azazello 3●2 accept rate: 0%
 0 somebody please help!! i dont get what wrong in my code(python). please... https://www.codechef.com/viewsolution/15429435 answered 15 Sep '17, 19:47 14●4 accept rate: 0% Well, You may have a look at my code variable m denotes the product, left holds the house number till we have checked and covered, and 100+m+1 is added to check for houses in the end, like 100, 99 ... Rest code is self-explanatory (java) https://www.codechef.com/viewsolution/15431189 (Solved this for you) Please UPVOTE.... Feel free to ask anything (16 Sep '17, 00:36)
 0 Well,the question and explanation in the example do not correlate .The question says in a straight line,a cop in a house can go left or right but not both whereas the explanation uses the range on either sides makig it a Simpler problem answered 09 Oct '17, 07:35 1★sussasun 1 accept rate: 0%

guyz here is a very easy solution in c++,go through it

include<algorithm>

using namespace std; struct dis { int max,min;

}; int main() { int t,m,x,y,p; cin>>t; for(int i=0;i<t;i++) {="" cin="">>m>>x>>y; p=x*y; int a[m]; int safe=0,h=0;

for(int j=0;j<m;j++)
{
cin>>a[j];
}
sort(a,a+m);
dis b[m];
int s,d;
for(int j=0;j<m;j++)
{
s=a[j]-p;// min
d=a[j]+p; //max
if(d>=100)
{b[j].max=100;}
else
b[j].max=d;

if(s<=1)

{b[j].min=1;}
else
b[j].min=s;
}
for(int j=0;j<m-1;j++)
{
if(b[j].max==100)
{
break;
}
if(b[j+1].min>b[j].max)
{
h=b[j+1].min-b[j].max-1;
safe=safe+h;
}
}
safe=safe+(b[0].min-1)+(100-b[m-1].max);
cout<<safe<<endl;


}

return 0;


}

This answer is marked "community wiki".

3★mk_g
23
accept rate: 0%

Better one I guess,never tried though

1. Hash the cop houses,better than Sorting(simply compensating the 400 bytes(sizeof(int)*100) for computing speed).
2. Consider the fact that Total Distance traveled by any cop is Distance=Number_Of_Houses_per_minute times Total_Time.
3. For any cop house consider that range inclusive [cop_house-Distance,cop_house+Distance] to be cop houses.
4. If there are any more left houses that is not included in the range,those are the best houses for the thief to hide.

Note:-

• For 100th cop house exclude right boundary.
• Step 4 can we achieved by some math directly for houses that aren't in the range.

1
accept rate: 0%

Is the time complexity correct?

Under faster solution its written - "Let us can create a sorted array of houses of cops." Wouldn't creating a sorted array contribute O(nlogn) to the total time? How is it just O(100*logn)

2★ragilr
12
accept rate: 0%

 0 @keertika32 I think you made an error in the inner for loop that is iterating from j=0 to j=4. Can you explain why you did that? answered 27 Mar '18, 00:55 4★elli0t 57●4 accept rate: 4%
 0 I have used prefix sum or something is better than that? answered 22 Sep '18, 18:17 0 accept rate: 0%
 0 I have used prefix sum or something is better than that? answered 22 Sep '18, 18:17 0 accept rate: 0%
 0 There is a relatively obvious answer which for speed doesn't depend on the number of houses at all and doesn't involve populating an array with likely-redundant entries. Sort the cop houses - $O(N\log N)$ - then step through these - $O(N)$ - to find the safe ranges.  lim = 100 for _ in range(int(input())): # input m,x,y = map(int, input().split()) cops = sorted( map(int, input().split()) ) # read and sort # process rng = x*y # the range of each cop hse = 1 # the next available house safe from the cops reviewed so far safe = 0 # count of safe houses for cop in cops: if cop-rng > hse: # there is a gap in cop coverage safe += cop-rng-hse hse = cop+rng+1 # current cop cannot reach this if hse<=lim: # some safe houses at the end too safe += lim-hse+1 # report print(safe)  answered 23 Sep '18, 07:09 5★joffan 948●8 accept rate: 13%
 0 what is wrong with this?? https://www.codechef.com/viewsolution/21204870 answered 25 Oct '18, 17:45 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,688
×48
×9

question asked: 30 Jun '15, 16:00

question was seen: 9,969 times

last updated: 25 Oct '18, 17:45