 UNPAIR - editorial

Practice

Contest

Author: Pankaj Jindal, Piyush Kumar

Tester: Sergey Kulik
Editorialist: Aman jain

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*[j] equals to M*[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*[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*[j] if M*[j] > 0. Correspondingly, each positive P(i,j) would represent edge with from node(i) to node(j) with weight P*[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*[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*[j] either M*[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** > 0, if we neglect self loops i.e. P**=0, this is because every even walk of length l, would make P^l** > 0. For ex: a->b->a is walk of length 2, so P^2** > 0, correspondingly SUM** > 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:
author
tester

I did the same as stated above by finding MST using Kruskal.
Why am I getting wrong answer?
http://www.codechef.com/viewsolution/6593707

When you say each element in P^k denotes the number of walks of length k from i o j, are you talking about length in terms of number of edges in the walk or length in terms of total weight of edges in the walk?

Number of edges in the walk.

If P*[j] is more than 1 (let us say 2), then it will mean that there are multiple edges between i and j (i.e. 2 edges). Then you have to consider number of walks taking care of multiedges may be because of syntax mistake,
if(c==1) cout<<2LL*ans<"
";

it should be if(c==1) cout<<2LL*ans<<"
";