Editorial for WC '17 Contest 2 S3 - Battle of the Pelennor Fields


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.

We can process the events one by one while maintaining information about the state of the battlefield in the form of two data structures. The first is a set O of points (integers) at which there are non-vulnerable orcs (note that the answer at any point is simply the size of O). The second is a set A of disjoint intervals (pairs of integers) of points in range of archers. Note that the intervals in A are closed (inclusive of its endpoints). Pre-populating A with a pair of dummy intervals [-\infty, -\infty] and [\infty, \infty] can make the following implementation more convenient. We'll want to implement both of these sets with balanced binary trees (e.g. C++ std::set) to allow for efficient insertion, deletion, searching, and ordered iteration.

It's important that the intervals in A are kept disjoint, such that no point on the number line is contained in multiple of them. For example, if there are two intervals [a, b] and [c, d] such that the latter is contained within the former (with a \le c and d \le b), then [c, d] should be removed completely. On the other hand, if they partially overlap with one another (with a \le c, c \le b, and b \le d), then they should be combined into a single interval [a, d].

Let's now consider how we can process the arrival of an orc at position o. We'll need to check whether or not this orc is already vulnerable (contained within an interval in A). This can be done in \mathcal O(\log N) time by searching for the interval [x, y] in A with the largest x value such that x \le o, and then checking whether o \le y. If not, then o should be inserted into O, also in \mathcal O(\log N) time.

What remains is being able to process the arrival of an archer at position a and with a bow range of r. This archer corresponds to an interval [x, y], where x = a-r and y = a+r. If [x, y] is already contained within an interval in A, then it can be completely disregarded. This can be checked in \mathcal O(\log N) time, very similarly to the above check for orcs.

Otherwise, the next step is to remove all orcs in O which are within [x, y]. To do so, we can search for the smallest point o in O such that o \ge x (if any), and repeatedly erase it and iterate to the next larger point in O until it's either greater than y or the end of O is reached. This process doesn't necessarily take \mathcal O(\log N) time for any given archer, as \mathcal O(N) orcs might be removed all at once, but it does take what's known as \mathcal O(\log N) amortized time, as each of the \mathcal O(N) orcs will be removed at most once in total. The result is that this step will take a total of \mathcal O(N \log N) time across all archers.

Finally, we need to update A according to the new interval. We should first iterate over existing intervals [x', y'] in A which overlap with [x, y] to the left (such that x' \le x and y' \ge x). For each such interval, we can erase it from A while combining it into the new interval by setting x = \min(x, x'). Similarly to the previous step, this process takes \mathcal O(\log N) amortized time per archer. The same approach should then be repeated for existing intervals overlapping [x, y] to the right, and then finally, the new combined interval [x, y] can be inserted into A, satisfying the guarantee that it's disjoint from all other intervals still in A.

The total complexity of the algorithm described above is \mathcal O(N \log N).


Comments

There are no comments at the moment.