×

# 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[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:
author
tester

This question is marked "community wiki".

561412
accept rate: 0%

2561314

 0 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 1★kevind 148●2●3●12 accept rate: 0% 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)
 0 When you say each element in $P^k$ denotes the number of walks of length $k$ from $i\to 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? answered 29 Mar '15, 14:25 81●1●4 accept rate: 9% Number of edges in the walk. If $P[i][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 :) (29 Mar '15, 14:32)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,250
×185
×72
×70

question asked: 25 Mar '15, 22:09

question was seen: 1,755 times

last updated: 16 Jun '15, 11:08