Dining Philosopher's Problem Adobe CODHERS Codesprint

Question Link - Dining Philosopher’s Problem

How to approach this problem?

I have opened the editorial and found the solution but I couldn’t make out of it how to convert it into code.

In the problem philosophers are sitting around a circular table. Now lets imagine they are sitting linearly along a straight line from index to 1 to N. Now let’s describe new array A:

In case that i-th philosopher eats, A_i = 1. In case that i-th philosopher doesn’t eat, A_i = 0.
We are interested for number of sequences A of length N such that no two neighbouring ones + in the case A_1 = 1 , A_N must be equal to 0 (in further text number valid sequences A).

Sub task for 50\% of score:

One of the approaches to solve this subtask is dynamic programming. Here we assume that philosophers are numbered from 1 to N. In dp function there are two parameters :

DP[i][x] is denoting amount of valid sequences such that A_1 = x, x = \{0,1\} .

If the i -th philosopher eats, then jump to the i + 2 -th philosopher, since now the i+1 -th philosopher can not eat. And if i -th philosopher does not eat, then jump to the i -th philosopher.

Final answer is DP[N][0] + DP[N-1][1] (in case A_1 = 1, A_N must be zero).

Please help this question I have been trying for a long time but not getting how to do it.

It’s all done with matrices.

Let’s solve a slightly easier problem where n philosophers are in a line. If there is one philospher, there are two possibilities, he can either eat or not eat:

\begin{pmatrix}1 \\ 1\end{pmatrix}

The top number in each vector is how many ways a philosopher can refrain from eating. The bottom number is how many ways they can eat. If we add a second philosopher, there are three possibilities, neither philosopher eats, the first philosopher eats, and the second philosopher eats. So there are two ways the second philosopher can not eat and one way he can eat:

\begin{pmatrix} 2 \\ 1\end{pmatrix}

We can work this out by looking at the previous vector. A third philosopher will be able to not eat in the 2 cases where the second philosopher is not eating, and will also be able to eat in the 1 case where the second philosopher eats, so 3 in total. But he will only be able to eat in the 2 cases where the second philosopher does not eat:

\begin{pmatrix} 3 \\ 2 \end{pmatrix}

In general, if there are x ways the rightmost philosopher can not eat, and y ways he can eat, there are x+y ways that an additional philosopher can sit down next to him and not eat, and x ways this additional philosopher can eat.

\begin{pmatrix} x \\ y \end{pmatrix} \to \begin{pmatrix} x+y \\ x \end{pmatrix}

You might notice that iterating this produces the Fibonacci sequence. This is because the formula we are using is the same.

Of course, the philosophers are not really in a line and the rightmost philosopher is actually sitting next to the leftmost philosopher. However, we can account for this by calculating twice, once where the leftmost philosopher does not eat and once where he does.

Let’s solve the problem for n=7:

\begin{pmatrix}1 \\ 0\end{pmatrix} \begin{pmatrix}1 \\ 1\end{pmatrix} \begin{pmatrix}2 \\ 1\end{pmatrix} \begin{pmatrix}3 \\ 2\end{pmatrix} \begin{pmatrix}5 \\ 3\end{pmatrix} \begin{pmatrix}8 \\ 5\end{pmatrix} \begin{pmatrix}13 \\ 8\end{pmatrix}

\begin{pmatrix}0 \\ 1\end{pmatrix} \begin{pmatrix}1 \\ 0\end{pmatrix} \begin{pmatrix}1 \\ 1\end{pmatrix} \begin{pmatrix}2 \\ 1\end{pmatrix} \begin{pmatrix}3 \\ 2\end{pmatrix} \begin{pmatrix}5 \\ 3\end{pmatrix} \begin{pmatrix}8 \\ 5\end{pmatrix}

Again, the top number in each vector is how many ways a philosopher can refrain from eating. The bottom number is how many ways they can eat. Each vector is calculated from the vector to it’s left.

I’ve done this twice, once where the first philosopher doesn’t eat and once where he does. Our answers are on the right hand side:

  • There are 13 ways for the 1st and 7th philosophers to not eat
  • There are 8 ways for the 1st philosopher to not eat and the 7th philosopher to eat.
  • There are 8 ways for the 1st philosopher to eat and the 7th philosopher not to eat.
  • There are 5 ways for the 1st and 7th philosophers to eat, if we forget for a moment that they are sitting next to each other.

Since the last case does not count, the answer is 13 + 8 + 8 = 29. Armed with this knowledge, you can score 44.53 points.


Can we do better? You’ve probably figured out how to calculate one vector from another, but you probably haven’t thought of doing it with matrices. You probably don’t know how matrices work either, so let me try to explain. This is how you multiply a matrix by a vector:

\begin{pmatrix}a & b \\ c & d\end{pmatrix} *\begin{pmatrix}e \\ f\end{pmatrix} =\begin{pmatrix}ae+bf \\ ce+df\end{pmatrix}

The matrix below can be used to calculate the next vector:

\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} *\begin{pmatrix}5 \\ 3\end{pmatrix} =\begin{pmatrix}5+3 \\ 5\end{pmatrix} =\begin{pmatrix}8 \\ 5\end{pmatrix}

Armed with your newfound knowledge of matrix-vector products, you can once again score 44.53 points. But you can also multiply matrices by matrices:

\begin{pmatrix}a & b \\ c & d\end{pmatrix} *\begin{pmatrix}e & f \\ g & h\end{pmatrix} =\begin{pmatrix}ae+bg, & af+bh \\ ce+dg, & cf+dh\end{pmatrix}

Note that you can treat the second matrix as two vectors \begin{pmatrix}e \\ g\end{pmatrix} and $\begin{pmatrix}f \ h\end{pmatrix}$and multiply both by the first matrix to get the same result.


The big secret is that multiplying this matrix product by a vector has the same effect as multiplying both vectors in turn by the matrix:

\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} *\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} =\begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix}

\begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix} *\begin{pmatrix}5 \\ 3\end{pmatrix} =\begin{pmatrix}10+3 \\ 5+3\end{pmatrix} =\begin{pmatrix}13 \\ 8\end{pmatrix}

So now we have a matrix that does what we want twice as fast. But why stop there? We can have a matrix that is four times as fast, eight times as fast, sixteen times as fast, and if we keep multiplying matrices by themselves we can quickly obtain vectors that are millions, billions, or even trillions of times faster than the one we started with.

What we do is called matrix exponentiation, and it can be done the same way as exponentiation on numbers. We start like this:

answer = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}, base = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} ,power = 6

answer is initialized to the identity matrix, which does nothing. Ostensibly, we want to multiply it by base six times. However, this is the same as multiplying by base^2 three times:

answer = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}, base = \begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix} ,power = 3

Now power is odd, so we multiply answer by base:

answer = \begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}, base = \begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix} ,power = 2

Once again, power is even, so we square base and halve power:

answer = \begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}, base = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix} ,power = 1

And finally we multiply answer by base for the last time:

answer = \begin{pmatrix}13 & 8 \\ 8 & 5\end{pmatrix}, base = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix} ,power = 0

Now we can solve the problem easily:

$ \begin{pmatrix}13 & 8 \ 8 & 5\end{pmatrix}

  • \begin{pmatrix}1 \ 0\end{pmatrix}
    = \begin{pmatrix}13 \ 8 \end{pmatrix}$

$ \begin{pmatrix}13 & 8 \ 8 & 5\end{pmatrix}

  • \begin{pmatrix}0 \ 1\end{pmatrix}
    = \begin{pmatrix}8 \ 5 \end{pmatrix}$

With this matrix exponentiation approach, you should be able to solve even n=10^{18} in milliseconds.

my code

1 Like

@bad_jim Thanks a lot. I understand the second part and exponential and all but I am having trouble understanding the first (vector part) how do you think of it. Its seems to me only Fibonacci sequence only but I am unable to relate it to answer.

Okay I’ve added a bit of explanation at the top for why we are calculating the Fibonacci sequence and how it relates to dining philosophers.

@bad_jim Wow!. Thanks a lot. I couldn’t express my gratitude. I was stuck on this question since I encountered two years back but wasn’t able to solve it. But your explanation is super easy and comprehensible. Again thanks.

//