Tuenti Challenge 6: Seat change! write-up

Posted on 6/10/2016 by José María Pérez, Software Engineer

Hi there! I'm the author of problem 15, Seat change! (as well as of problem 6). Here is a small write-up of this problem: 

When we change seats at Tuenti, a friend always jokes about the tea party scene in Disney’s Alice in Wonderland and, in the past, I've worked with matrix multiplication... why not combine both of them in this challenge?

In this problem, you have chairs, probabilities of going from one chair to another chair and a number of seat changes. If you can recognize a Markov Chain in this problem, you’re spot on. If you did not recognize it, don’t worry, the math is pretty basic:

Suppose that you organize the probabilities of going from one chair to another after one seat change in a matrix, where rows are starting chairs and columns are ending chairs. If you multiply that matrix by itself, you will get the probability after two seat changes.
In fact, the problem is asking you about the index for the max element in a row of matrix^number_of_seat_changes, using integers to maintain the precision.

Multiplying two square matrices has a complexity of O(size³) (less if you use certain algorithms, but this is not the objective of the problem) and there are some optimizations that are useful:

Depending on whether N is even or odd:
    matrix^N = (matrix^(N/2))²
    matrix^N = (matrix^((N-1)/2)² * matrix
This reduces the complexity of the number of matrix multiplications from O(N) to, O(log2(N)) (at the expense of storing intermediate matrices), and it was intended to be needed in order to solve the problem.

Another useful optimization is breaking the connection matrix into its connected components and computing them separately. For example, if you have N chairs in two connected components, one of them of size M, the complexity of the matrix multiplication is reduced from O(N³) to O(M³) + O((N-M)³). As the matrices do not change between tries, you can check if this optimization is useful before coding it (Hint: it is). It also has the benefit that you may not need to exponentiate both matrices to the same exponents.

With those two optimizations, and caching the intermediate results, you could solve the problem with the hard input in a reasonable time (my solution does it in less than one minute).

Well, that's it for today. I hope you liked it and remember:
We're all mad here.
- Lewis Carroll, Alice in Wonderland

Follow us