Editorial for DMOPC '20 Contest 4 P3 - Roving Roombas
Submitting an official solution before solving the problem yourself is a bannable offence.
We can mark all the squares with the Roombas and then for each cord, check how many squares contain the path of a Roomba.
We could line sweep, but the easier solution for this subtask is to simply check every Roomba and cord pair and determine if they intersect. A Roomba intersects cord if and .
If we look at the inequality used for the previous subtask, we note that we benefit greatly from sorting. Let's sort both the cords and the Roombas by . As we walk along the cords from left to right, we know that certain Roombas become irrelevant, since their paths are too short.
If we have a set of Roombas and a given cord, we can determine which Roombas intersect easily with a BIT. As we walk left to right, we remove certain Roombas from the set by updating the BIT. We query for all Roombas with small enough values by querying the BIT.
We can finish off this solution with a line sweep. Note that any that does not appear for any Roombas nor any cords is irrelevant, and similarly with .
An alternative, very similar solution is to use binary search instead of a BIT. The effect is the same.