Editorial for WC '17 Contest 2 S3 - Battle of the Pelennor Fields
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 of points (integers) at which there are non-vulnerable orcs (note that the answer at any point is simply the size of ). The second is a set of disjoint intervals (pairs of integers) of points in range of archers. Note that the intervals in are closed (inclusive of its endpoints). Pre-populating with a pair of dummy intervals and 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 are kept disjoint, such that no point on the number line is contained in multiple of them. For example, if there are two intervals and such that the latter is contained within the former (with and ), then should be removed completely. On the other hand, if they partially overlap with one another (with , , and ), then they should be combined into a single interval .
Let's now consider how we can process the arrival of an orc at position . We'll need to check whether or not this orc is already vulnerable (contained within an interval in ). This can be done in time by searching for the interval in with the largest value such that , and then checking whether . If not, then should be inserted into , also in time.
What remains is being able to process the arrival of an archer at position and with a bow range of . This archer corresponds to an interval , where and . If is already contained within an interval in , then it can be completely disregarded. This can be checked in time, very similarly to the above check for orcs.
Otherwise, the next step is to remove all orcs in which are within . To do so, we can search for the smallest point in such that (if any), and repeatedly erase it and iterate to the next larger point in until it's either greater than or the end of is reached. This process doesn't necessarily take time for any given archer, as orcs might be removed all at once, but it does take what's known as amortized time, as each of the orcs will be removed at most once in total. The result is that this step will take a total of time across all archers.
Finally, we need to update according to the new interval. We should first iterate over existing intervals in which overlap with to the left (such that and ). For each such interval, we can erase it from while combining it into the new interval by setting . Similarly to the previous step, this process takes amortized time per archer. The same approach should then be repeated for existing intervals overlapping to the right, and then finally, the new combined interval can be inserted into , satisfying the guarantee that it's disjoint from all other intervals still in .
The total complexity of the algorithm described above is .
Comments