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

Question

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$, the attack is successful, and at the end of the day, the wall will be built up such that any segment of it within $[W,E]$ of height $< S$ would then be at height $S$ (or greater, if some other attack that day hit upon the same segment with strength $S' > 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 - $O(A \log A)$
• For each attack, see if it would be successful ($\log X$ query time). When the day changes, loop through all unprocessed successful attacks and update the wall accordingly ($\log X$ update time for each attack). - $O(A\log X)$

My question is this: Is there a way to do better than $O(A\log A + (A+X)\log X)$? Perhaps, is there some strategic way to take advantage of the linear nature of Tribes' successive attacks? 20 seconds feels too long for an intended solution (although Java might be to blame for that).

Answer 1

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.

Answer 2

The following was removed from the question, as it is an answer.

Looking over other discussions and successful solutions seems to indicate that the solution I've described is pretty much the expected algorithm. The slow-down in my solution is possibly just due to lazy use of auto-boxing and a pointer-based tree structure, rather than an array-based one - so I suspect that, if a solution does exist, it's probably not a whole lot better than what's here.

The solution can be found here. It's very much the same as what I have posted here; so I am much more inclined to believe that a more efficient solution does not exist.