Problem Link :
Author : Jatin Yadav
Tester : Misha Chorniy
Editorialist : Anand Jaisingh
Pre-Requisites :
Matrices, Cayley Hamilton theorem, Polynomial Interpolation
Problem :
Given a tree consisting of N nodes rooted at node r, find the number of walks of length K between node r and all nodes of the tree.
Explanation :
I think finding the number of walks of length K in an arbitrary graph between 2 nodes i,j is a well known problem, and can be solved in O(N^{3} \cdot log_{2}(K) ) using matrix exponentiation. For example, you can read about it here
Basically, let matrix M be the adjacency matrix of a given graph G. For example, consider the tree given in the sample of the problem statement. It’s adjacency matrix is :
\begin{equation}
\begin{pmatrix}
0 & 1 & 1 & 1 & 0 \newline
1 & 0 & 0 & 0 & 0 \newline
1 & 0 & 0 & 0 & 0 \newline
1 & 0 & 0 & 0 & 1 \newline
0 & 0 & 0 & 1 & 0
\end{pmatrix}
\end{equation}
Now, the number of paths of length K between some fixed vertex i and all vertex j is given by the product M^{K} \cdot V, where the i^{th} component of column vector V of size N is 1, and all others are 0.
So, we can solve the 1^{st} sub task using this method, exponentiating the adjacency matrix.
For the second sub task, we find that its going to be very hard to find M^{K} in the given TL. To pass this sub task, we can use DP, where :
Dp[r][0]=1
Dp[i][j]= \sum_{u} dp[u][j-1], for all u adjacent to i and j \ge 1 .
Now, coming to the 3^{rd} sub-task, we find that none of the above 2 methods are going to be sufficient. We need to do something more technical. Important Observation : The graph given in the input is always a tree, and not any arbitrary graph.
Also, one more important observation we can make is that in the last part of the matrix exponentiation, we are doing a lot of use-less multiplications, since the vector V consists of only 1 non-zero entry. Basically, only the elements of the r^{th} column of M^{K} are needed, since all other entries are always multiplied by 0.
Now, before proceeding further, you need to read about cayley hamilton theorem, from here and here
In-fact, we can use this to solve the problem. A theorem, Cayley Hamilton theorem can be used to find a single row or column of this matrix in O(N^2) time, but only if we can find its characteristic polynomial in such time too. Something that we need to be aware of is that if we can find the characteristic polynomial of a matrix, then we can express the powers >= N of a matrix in terms of the first N-1 powers of the matrix. This is because of the fact that each matrix satisfies it’s own characteristic polynomial.
However, the given blog link above deals only with the case of one dimensional linear recurrence. Our Recurrence is two dimensional, and until now, we have not found a method to find the characteristic polynomial.
Now, you need to read about polynomial interpolation before proceeding further.
Now, there are research based techniques based on finding the characteristic polynomial of a tree, it presents a neat and detailed way to find what we required. It is going to be useless for me to mention all those details all over again for me when I myself read it there, so you can access 2 of them here and here
Now, once we have found the characteristic polynomial, things should be easy to do. We can find the linear combination of I_{N},M,M^2,...M^{N-1} that equals M^K. Let this representation be [c_0,c_1,...c_{N-1}]. We can do this step in O(N^2 log_2 {K}) time.
So, M^{K}= \sum_{i=0}^{N-1} c_i \cdot M^i
However, we only need the r^{th} column of M^{K}, so , if we can calculate the r^{th} columns of I, M , M^2 ...M^{N-1}, then we’re good to go, we can just add the columns with their weight, i.e c_i for the i^{th} matrix. We can find the r^{th} column of all M,M^2,...M^{N-1} in O(N^2), but how ?
First, we know the r^{th} column of I_{N}. Assume we know the the r^{th} column of M^i, let’s prove we can find the r^{th} column of M^{i+1} in O(N) by induction :
M^{i+1}[x][r] = dot product of x^{th} row of M and r^{th} column of M^i. But, instead of calculating the dot product in a naive way, we can only go over the non-zero entries of the x^{th} row of M, For example :
M^{i+1}[x][r] = \sum_{u} M^{i}[u][r], for all u adjacent to x, since these are the only non-zero entries in row x of matrix M. To calculate all M^{i+1}[x][r], x=1,2,...N, this requires is O(N) operations. So to do this over all M,M^2,...M^{N-1}, we require O(N^2) time.
Now, the answer for node i is simply M^{K}[i][r]. If you need to familiarize yourself with cayley hamilton theorem first, then try this project euler problem.
Overall Complexity : O(N^2 \cdot log_{2}(K) )