Problem of the Week: On Modular Arithmetic

This week, we’ll be analyzing an algorithmic challenge from the recent TCO19 Round 1B of the Algorithm Track, “EllysTeleport” - https://community.topcoder.com/stat?c=problem_statement&pm=15422&rd=17509

The summary of the problem statement is -

There are N platforms in a video game, each placed on top of each other. The height of the lowest platform is H1, and the other heights are computed with the equation: height[i] = (height[i-1] * A + B) % M

Each platform has a coin.

We, the player of this video game, can place our hero at any platform initially. Our hero teleports from a platform X, to a height Y = (X * P + Q) % M.

If Y is not the height of a platform, he will fall down until he reaches the platform immediately below him. Upon falling on an unvisited platform, the hero collects the coin on this platform.

Our hero repeatedly teleports until he either has picked up all coins or until he teleports below H1 in which case the game ends.

The problem statement now asks us, what is the maximum number of coins the hero can collect, should the hero start at the optimal platform.

The first observation to be made is that there are only two possibilities from a given platform.

• The hero’s path becomes cyclic due to the modulo arithmetic nature of the equation and the hero repeatedly visits only a certain set of platforms.

• Due to the modular arithmetic, the hero teleports to a height less than H1 and the game ends.

It’s easy to see why the path can become cyclic in case 1 as we repeatedly perform the modulo operation, all values are restricted to 0 to (M-1), thus eventually at least one value is bound to repeat by the pigeonhole principle, defining the start of the cycle.

If we can compute what the optimal answer would be given we start from a specific platform, then our final answer will be the maximum of all these potential answers.

The simplest way to simulate this is by identifying which platform will the hero effectively teleport to from each platform, and performing a depth-first-search in this manner.

This can be done by preprocessing all heights of the platforms initially -- let us store these heights in a vector “h”.

Now for each platform, we know that the hero will teleport to a height Y = (X * P + Q) % M where X must be the height of the current platform.

Thus we can binary search for the largest height in h, that is not greater than Y, and this will indicate which platform the hero teleports to from the current platform.

Let us store this in a vector “go” (implying which platform our hero will next GO to).

Also, should Y be equal to a value less than H1, then we’ll denote this by storing a “-1” value in our “go” vector.

Now that we’ve processed each platform’s immediate next platform, we simply need to find the longest path from the given implicit graph we have created (where the “go” vector stores our current platform/node’s child).

This can be done by running a depth-first-search on each unvisited node (platform) and we’ll update our final answer by taking the maximum of all answers obtained from this DFS.

The fastest submission was by yuxiaogang who solved this challenge in under 9 minutes!

Find his submission over here - https://community.topcoder.com/stat?c=problem_solution&cr=40810946&rd=17509&pm=15422