HackerRank The Chase Writeup

4 minute read Updated 2019-03-20

A long long time ago I solved The Chase (Project Euler 227) on HackerRank. It took me a long time to figure it out, so I wrote up these notes.

Bayleef amended the problem from the original and it is a bit more complicated. Namely, it requires an exact answer. And the inputs can be rather large, so we need to make sure our algorithm is efficient.

The problem

An even number of players are playing The Chase. At the start, two players on opposite sides of a table are each given m-sided dice. On each turn, both players roll the dice. If it lands on 1, they pass it to the player on their left. If it lands on m, they pass it to the player on their right. The game ends when one player has both dice at the end of a turn.

We need to answer: for n players and m-sided dice, how many turns will the game last?

Modulo 10⁹ + 9

The numbers we could be dealing with in our solution could get quite large so the result is returned modulo 10^9 + 9. In this case, you can think of modulo as a checksum. The result is that the biggest numbers used in the solution will fit into a long long and most variables will fit into an int.

You can learn more about why modulo is needed and how to approach questions involving it in A. Sharma's article. However, I'll outline the basics here.

The first important thing to note is that the question requires an exact answer. If you have a solution to the original Project Euler problem, you probably took an approach which gave an approximate answer (to the precision specified in the original problem). That's not going to work here. To start figuring out an approach, you might want to look at Markov chains.

The modulo operation has the following distributive properties:

(a + b) % c == ((a % c) + (b % c)) % c
(a - b) % c == ((a % c) - (b % c)) % c
(a * b) % c == ((a % c) * (b % c)) % c

However, modulo is not distributive over division:

(a / b) % c != ((a % c) / (b % c)) % c

To approach division under modulo, we instead multiply by the inverse of the divisor:

a / b == a * b^-1

We call b^-1 the multiplicative inverse, and there are several algorithms available to help us calculate it (I'll leave you to decide which to use). Rather than use division we can now multiply by the multiplicative inverse.

Optimisations

To enable your code to successfully process larger inputs within the available time and memory limits you'll need to optimise.

My first piece of advice is to write your solution in a fast language. I originally wrote mine in Python 3 but it timed out for test case #36 and onward. I rewrote the algorithm in C++ and successfully completed all the test cases.

However, this might say more about the inefficiency of my algorithm (rather than Python). oleg_b commented in the discussion that there is a Python2 solution that has a worst runtime of 2.6 secs.

The next is to write out the matrix you are trying to solve (using a placeholder for the values). By doing this you should be able to notice a number of optimisations in terms of memory usage and the number times your code loops.

The problem

Modulo 109 + 9

Optimisations

Further reading

Modulo 10⁹ + 9