Editorial for The New Kid

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: d, Plasmatic

For the purpose of this editorial, houses that contain people Jagdeep doesn't like will be known as 'bad houses'

Solution 1 (d)

For each empty house, compute the closest distance from it to a bad house. Select the empty house that has the greatest computed distance. If two empty houses are tied, then select the empty house that is closer to the front of the street.

Time Complexity: \mathcal O(NM)

Solution 2 (Plasmatic)

First, note that for each empty house, the only bad houses that matter are the ones that are the closest to them.

We can sort the list of bad houses and then binary search for the location of each empty house. This gets the index to the first bad house with a location greater than that of said house. We can then just subtract the index by one to get the other closest bad house.

Now, finding the empty house furthest away from a bad house is now easy, we just need to find the one with the maximum distance away from its closest bad houses.

Note: for the binary search, you will have to account for cases where the binary search returns the first or last index.

Time Complexity: \mathcal O(M \log M + N \log M)


There are no comments at the moment.