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).