Say we have $n$ rooms, goes from room $i$ to room $j$ can gain $k$ dollars. For example, the following matrix:
$$ \begin{matrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 20 \\ 0 & 0 & 0 & 2 \end{matrix} $$
the matrix entry for row $i$ and column $j$ indicates the amount of money received by going from room $i$ to room $j$ (or staying in the same room if $i = j$. And we have only $t$ turns. (Always start from room 1)
The maximum money we can gain from the above is matrix is 42 under 5 turns. (From room 1 to room 3 (0 money), room 3 to room 4(20 money), room 4 to room 3 (20 money), room 3 to room 4 (40 money), room 4 to room 4 (42 money).
I am trying to solve this problem using a hint, which says:
The question of finding distances of paths of a given length is equivalent to a certain "matrix multiplication" using max and '+' instead of '+' and '*' respectively. Then you need to compute a matrix power, which should be done by "binary powering" (aka "repeated squaring)
However, I tried to compute this certain matrix multiplication, but I have no idea the meaning of applying matrix power. Any suggestions are appreciated.
Think about how matrix multiplication works. You take the first row of the first matrix and the first column of the second matrix and you go through the entries one at a time, multiplying the corresponding elements of the row and the column, and in the end adding them. You do this again for each pair of a row and a column. That is, the element in the $i$th row and $j$th column is the sum over $k$ of the element in the $i$th row and the $k$th column in the first matrix times the element in the $k$th row and the $j$th column in the second matrix. To take powers of matrices, you just multiply the matrix by itself.
So now let’s look at the matrix “multiplication” described in the problem. Instead of multiplying the row element with the column element, you add. And I stead of adding the products you just got, you take the max. How does this work? We should think of the $i$th row $j$th column as the maximal amount of money you can get in going from room $i$ to room $j$ in the requisite amount of turns.
For example: if we just take the first “power” of $A$, there’s no way to get from room $i$ to room $j$ besides just going there straightaway. So this works. Similarly, if we look at $A^2$, the most money you can earn going from room $i$ to $j$ comes from taking the most you can’t make by going first through some auxiliary door $k$, and finding the max of the total money going from $i$ to $k$ and then from $k$ to $j$ is both what you must do, and what the matrix calculation does inherently.
Similarly, if you have a listing of the most money you can obtain going from $i$ to $k$ in $n$ steps, then multiplying by $A$ again just does the same thing: going from $i$ to $j$ in $n+1$ steps, you must enter $j$ on your last step, and if you were at $k$ before that, you must find the max amount of money you can earn going from $i$ to $k$ in $n$ turns plus going straight from $k$ to $j$. The max-sum operation does this for you. So the point is that taking “powers” of $A$ in this manner gives you a matrix telling you how much money you can make going from each room to each other room in any number of steps you want.