Is there a faster solution for the Google Code Jam Great Wall Problem

Consider the following Google Code Jam round 1C question:

The Great Wall of China starts out as an infinite line, where the height at all locations is $0$.

Some number of tribes $N$, $N \le 1000$, will attack the wall the wall according to the following parameters - a start day, $D$, a start strength $S$, a start west-coordinate, $W$, and a start east-coordinate, $E$. This first attack occurs on day $D$, on range $[W,E]$, at strength $S$. If there is any portion of the Great Wall within $[W,E]$ that has height $ S$)

Each tribe will perform up to $1000$ attacks before retreating, and each attack will be determined iteratively from the one before it. Every tribe has some $\delta_D$, $\delta_X$, and $\delta_S$ that determines their sequence of attacks: The will wait $\delta_D \ge 1$ days between attacks, they will move their attack range $\delta_X$ units for each attack (negative = west, positive = east), though the size of the range will stay the same, and their strength will also increase/decrease by a constant value after each attack.

The goal of the problem is, given a complete description of the attacking tribes, determine how many of their attacks will be successful.

I managed to code a solution that does work, running in about 20 seconds: I believe the solution I implemented takes $O(A\log A + (A+X)\log X)$ time, where $A =$ the total number of attacks in a simulation (max $1000000$), and $X =$ the total number of unique edge points on attack ranges (max $2000000$).

At a high level, my solution:

• Reads in all the Tribe information

• Calculates all the unique $X$-coordinates for attack ranges - $O(A)$

• Represents the Wall as a lazily-updated binary tree over the $X$ ranges that tracks minimum height values. A leaf is the span of two $X$ coordinates with nothing in-between, and all parent nodes represent the continuous interval covered by their children. - $O(X \log X)$

• Generates all the Attacks every Tribe will perform, and sorts them by day -

The obvious room for improvement is this step:


Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A\log A)$

We know that the tribes will attack from a particular day, in regular intervals. That means we should be essentially merging lots of pre-sorted lists. Also the problem statement tells us that there will never be more than 1,000 tribes (i.e. 1,000 lists to merge); a tiny number compared with the 1,000,000 maximum attacks! Depending on your implementation's relative timings, switching this could cut the processing time in half.

That's really all I can suggest for optimising the theoretical complexity, but I have no proof that it would be optimal after this change.

I gave the puzzle a go myself, but I used a much dumber representation of the wall: a binary search tree (C++'s std::map to be precise) storing locations where the wall's height changes. With this, I was able to add and removed nodes as required (i.e. if a complicated section was subject to a large, overwhelming attack, or multiple attacks of the same strength touched, the number of nodes would reduce significantly). This solved the large input in 3.9 seconds (on my mid-spec development laptop). I suspect there are several reasons for the improvement:

• As you pointed out, boxing and unboxing can get expensive, but C++'s template-based containers avoid this entirely.

• While the wall representation I used is theoretically worse, in the vast majority of cases being able to dynamically reduce the number of nodes made it super-fast (most test cases maxed-out at under 1k nodes, and all but 2 were under 10k). In fact, the only case which took any significant time was #7, which seems to have been testing lots of non-intersecting ranges.

• I used no pre-processing (stages are determined by keeping track of when each tribe will next attack, and searching for the joint-lowest each turn). Again this is theoretically worse, but for the majority of cases I suspect the lower overhead means it was faster (I'll test this and get back to you). Update: I added a priority queue for attacks, similar to the method described above (although instead of creating the large array I calculated it on-the-fly) and saw the time decrease to 3.0 seconds for the large input.

In short, while I think your algorithm is near-optimal in the general case, there are several ways you could speed it up for typical inputs.

StackExchange Computer Science Q#12040, answer score: 2