PROBLEM LINK:
Author: Pankaj Jindal, Piyush Kumar
Tester: Sergey Kulik
Editorialist: Aman jain
DIFFICULTY:
medium-hard
PREREQUISITES:
Minimum Spanning Tree(MST), Matrix Exponentiation and its relation to count number of walks in a graph.
You can learn about Matrix Exponentiation and
MST here.
PROBLEM:
Given a N*N symmetric matrix M , construct a matrix P such that P is also symmetric, P[i][j] equals to M[i][j] or 0 and SUM = P^{1}+P^{2}+......+P^{S} > 0 for some S > 0. You need to minimize the sum of all elements of P.
QUICK EXPLANATION:
Each value pair (i,j) in matrix M defines a edge of length M[i][j]. Then, P should be a matrix that represents MST on matrix M.
EXPLANATION:
Our aim is to construct a matrix P from M such that sum of all elements of P is minimum.
Here matrix SUM > 0, means each and every element of SUM matrix is greater than 0.
Let each element M(i,j) be a edge from node(i) to node(j) with weight M[i][j] if M[i][j] > 0. Correspondingly, each positive P(i,j) would represent edge with from node(i) to node(j) with weight P[i][j].
According to theory of Matrix Exponentiation, each element in P^{k}, would represent number of walks of length k from node(i) to node(j). SUM[i][j] = 0, would mean that number of walks of non zero length between node(i) and node(j) is zero. It means that node(i) and node(j) are not connected to each other. So the underlying graph for representing P should be connected. Otherwise there will be zero entries in SUM matrix.
For the first subtask, N <= 5, which means number of elements in M is atmost 25 and since matrix M and P are symmetric, we need to consider diagonal and upper-diagonal elements for making P i.e. total of N*(N+1)/2 elements. We have two choices for P[i][j] either M[i][j] or 0 i.e. atmost 2^{N*(N+1)/2} possibilities. From above discussion, we know that graph represented by P has to be connected to make SUM > 0, so from all possibilities choose P which is connected and has minimum sum, that would be our solution. Complexity should be O(2^{N*(N+1)/2}*N*(N+1)/2), which is about 5*10^{7} computations that will run within limit for first sub-task but poorly performs on final task.
It is clear that optimal P is connected graph with minimal total sum of its edges, if you see this is the definition of MST. Here you may think that why we are ditching self-loops and how SUM[i][i] > 0, if we neglect self loops i.e. P[i][i]=0, this is because every even walk of length l, would make P^l[i][i] > 0. For ex: a->b->a is walk of length 2, so P^2[i][i] > 0, correspondingly SUM[i][i] > 0 for S >= 2.
Since matrix P is symmetric, sum of all its elements would be twice the sum of edges in MST.
COMPLEXITY:
Number of Edges(E) in our graph is N^{2}, constructed from M.
Number of Vertices(V) in our graph is N.
Complexity of constructing MST is O(Elog(E) + Elog(V)) i.e. O(N^{2}log(N)), which is the overall complexity of our solution.
AUTHOR’S, TESTER’S SOLUTIONS:
