## IPSC 2017

## Solution to Problem E – Elevation alteration

Let’s consider what happens on every command. If we want to raise a point by 1 meter, and both its neighbors are on the same level or higher than it, then it’s easy – we can just raise that point. If a neighbor is already lower than us, we must also raise that neighbor, and keep raising points in that direction until we find a neighbor that’s equal or higher. For every command, we might have to change the elevation of many points.

But what if instead of remembering the elevation at every point, we just remember the slopes between neighbors? For example, instead of (10, 10, 11, 12, 12, 11, 10, 9, 8, 9) let’s remember (0, 1, 1, 0, -1, -1, -1, -1, 1).

With this point of view, raising a point works like this:

- Find the nearest slope to the right of our point whose value is not -1. (This slope is between the last point we’re raising and the closest point we don’t have to raise.)
- Decrease that slope by 1.
- Find the nearest slope to the left of our point whose value is not 1.
- Increase that slope by 1.
- The cost can be calculated from the distance of the two slopes you changed.

Lowering a point is the opposite.

This can be done quickly by using a map (a.k.a. tree map, a.k.a. balanced search tree). Instead of storing all the slopes in an array, we can do “run length encoding” and store every continuous run of equal values as a single entry. This can be quickly queried and updated. The time complexity is *O*(*n* log *n*), because the terrain is initially flat and every command can change at most two slopes.