Editorial for DMOPC '20 Contest 4 P3 - Roving Roombas

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.

Author: Riolku

Subtask 1

We can mark all the squares with the Roombas and then for each cord, check how many squares contain the path of a Roomba.

Time Complexity: \mathcal O(NX_i + MY_i)

Subtask 2

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 (R_x, R_y) intersects cord (C_x, C_y) if C_y \ge R_y and R_x \ge C_x.

Time Complexity: \mathcal O(NM)

Subtask 3

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 X. 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 Y values by querying the BIT.

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

Subtask 4

We can finish off this solution with a line sweep. Note that any X that does not appear for any Roombas nor any cords is irrelevant, and similarly with Y.

An alternative, very similar solution is to use binary search instead of a BIT. The effect is the same.

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


There are no comments at the moment.