I just solved The Chase (Project Euler 227) on HackerRank. Since some people have had a hard time figuring out an approach to this problem, I’m going to outline mine. While I won’t give an exact solution, if you haven’t attempted this problem (or the Project Euler version), please try it before you read on.
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.
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 109 + 9
The numbers we could be dealing with in our solution could get quite large. Since Bayleef is more interested in our ability to write an algorithm to solve the problem, rather than perform math on really large numbers, the problem requests the answer 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
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 study 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.
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 – I’d love to see that approach!
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.
I hope that this gives you some extra insight into how to solve the problem without taking away all the fun. If you’d like to learn more about the techniques I used then I suggest reviewing the following:
- Introduction to Probability by C. Grinstead and J. Snell - Chapter 11 Markov Chains
- Why “OUTPUT THE ANSWER MODULO 10^9 + 7”? by A. Sharma
- Linear Algebra and Its Applications by G. Strang (4th ed) - 1.6 Inverses and Transposes
- Modular multiplicative inverse on GeeksforGeeks