PROBLEM LINK: Author: Pankaj Jindal, Piyush Kumar DIFFICULTY:mediumhard PREREQUISITES:Minimum Spanning Tree(MST), Matrix Exponentiation and its relation to count number of walks in a graph. 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. 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 upperdiagonal 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 subtask 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 selfloops 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$.
This question is marked "community wiki".
asked 25 Mar '15, 22:09

I did the same as stated above by finding MST using Kruskal. Why am I getting wrong answer? http://www.codechef.com/viewsolution/6593707 answered 29 Mar '15, 14:13
may be because of syntax mistake, if(c==1) cout<<2LL*ans<"\n"; it should be if(c==1) cout<<2LL*ans<<"\n";
(29 Mar '15, 15:22)
