Internet Problem Solving Contest

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:

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.