### PROBLEM LINK:

**Author:** Devendra Agarwal

**Tester:** Surya Kiran

**Editorialist:** Amit Pandey

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

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