# Monster Capturing

About a week ago, one of my friends (who I met at stage two of this year’s CCC – fun times, fun times) posed an interesting problem to me, which I will try to summarize below:

Alice and Bob are professional monster trappers, but occasionally, even they get stuck in difficult scenarios. In this world, Alice is currently at a location denoted by $(0,0)$ (think of a grid). $P$ monsters exist at certain locations, and there’s a maximum of one monster at a given location. Bob is on a plane right now, and he wants to ask: if I fall down and land at location $(x,y)$, how many monsters will lie between me and Alice (where “between” means if a monster is at $(m,n)$, then it’s “between” if $0 \leq m \leq x$ and $0 \leq n \leq y)$? Note that Bob will ask the question many, many times ($Q$ times), all with different values of $(x,y)$. (Also: $0 \leq x,y,m,n,P,Q \leq 30000$)

For the seasoned contest programming veteran, the question immediately reduces down to: given 30 000 of coordinates that fall within a range of 30 000 by 30 000, we must efficiently perform 30 000 queries, such that each query returns the number of coordinates below-or-at and left-or-at of the query location (we should always assume the biggest numbers). Thus, the super-naive $O(PQ)$ algorithm (~900 million calculations), where we iterate over all coordinates for each query, is too slow for the conventional 1-CPU-second time limit.

I loved this question, because there’s such an obviously sub-optimal classic data structure to solve it – the 2D binary index tree, or Fenwick tree (if you’re not sure what that is, here’s an excellent tutorial). The naive solution is simple, as follows:

First, make a 2D binary index tree of size 30 000-by-30 000. Proceed to add all the monsters into that tree (this takes $O(P\log ^2 P$), for $P$ insertions, each taking $\log ^2 P$ time). Then, we can run $Q$ queries on the tree, each taking $\log ^2 P$ time, so this takes $O(Q\log ^2 P)$. Overall, $O((Q+P)\log ^2 P)$, which is about 12 million primitive operations, a very respectable time (about 0.2 s, by my estimate).

However, the problem is that you can’t really make a 30 000-by-30 000 tree – not unless you’re given close to a gigabyte of memory! Since we’re usually given only 200 MB or so, a 2D tree fails spectacularly.

I admit, this problem puzzled me quite a bit, because I simply couldn’t see a solution without a 2D tree. Coordinate compression came to mind, but that didn’t seem to help significantly either. But then I thought back to my USACO days, and an “aha!” moment came in a flash. Here’s my solution:

First, we put everything in an array of size 60 000, monsters and queries, each in a 3-tuple of form $(x, y, r)$, where $x,y$ are the coordinates and $r$ is a number: 0 if a monster, 1 if a query. We sort it, with the leftmost coordinates first, and if tied, bottommost first, and so on (C++’s std::sort is a wonderful way to sort a pair<pair<int,int>, int> type like this, by the way). We also form a 1D binary index tree of size 30 000, which will keep track of how many monster below a certain y-coordinate we have seen already. Now, we do a plane sweep (shout-out to USACO for teaching me this!) by iterating over the array: if we see a monster, we add its y-coordinate to the tree. If we see a query, then we simply query the tree for the number of monsters, since we know that the monsters already seen are to the left of the query. Thus, the runtime of this algorithm is $O((P+Q)\log(P+Q))$, dominated by the sorting (array processing is “only” $O((P+Q)\log P))$. This solution clearly runs under the memory and time limits.