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

Time Complexity: $\mathcal O(NM)$ ~\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$ ~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$ ~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$ ~X~ that does not appear for any Roombas nor any cords is irrelevant, and similarly with $Y$ ~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)$ ~\mathcal O(N \log N + M \log M)~

Comments

1

Badmode commented on Feb. 23, 2022, 4:35 a.m. ← edited →

How would binary search be used with a line sweep? I was thinking of storing the roombas in a vector, and as I travel from left to right, I erase roombas where $R_y < C_y$ ~R_y < C_y~ because the path is too short to be considered, but erasing elements is $\mathcal{O}(n)$ ~\mathcal{O}(n)~...
Any hints? Thanks.

3

Lost commented on Feb. 23, 2022, 1:45 p.m.

The line sweep iterates the events sorted by their $x$ ~x~ position. Events are either a cord at or Roomba endpoint. You can store the $y$ ~y~ positions of the Roombas that have not reached their endpoint yet. This means that at the start, all the Roomba $y$ ~y~ positions will be stored.

When you reach a cord event, you can binary search for the amount of Roomba $y$ ~y~ positions less than the cord's $y$ ~y~ position. These are all the Roombas that will intersect the current cord. When you reach a Roomba endpoint, you delete it's $y$ ~y~ position. You can also use a BIT to query the amount of Roomba $y$ ~y~ positions less than a cord $y$ ~y~ position and decrement Roomba $y$ ~y~ values. It's not recommended to use a vector to store values because it's erase is $\mathcal O(N)$ ~\mathcal O(N)~.

1

Badmode commented on Feb. 24, 2022, 3:02 a.m. ← edited →

What data structure suffices with the binary search option?

Edit: ORZ Lost

2

Lost commented on Feb. 24, 2022, 1:32 p.m. ← edit 4 →

A standard C++ set almost suffices. It has $\mathcal O(\log N)$ ~\mathcal O(\log N)~ insert, erase, and an upperbound (binary search) function. The issue is this upperbound function returns an iterator to the element and unlike vector iterators, you can't find the index of this iterator (it - vectorname.begin()). This means you will have to use a set from the gnu pbds library. It has an order_of_key(k) method that finds the number of elements strictly less than $k$ ~k~. Now you can use order_of_key(k+1) to find the amount of elements $\le k$ ~\le k~, because running over the end of a cord also counts as an intersection.

Gnu pbds set: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/