You are not logged in. Please login at www.codechef.com to post your questions!

×

UNPAIR - editorial

PROBLEM LINK:
Practice
Contest

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

This question is marked "community wiki".

asked 25 Mar '15, 22:09

amanjain110893's gravatar image

4★amanjain110893
561412
accept rate: 0%

edited 16 Jun '15, 11:08

vicky002's gravatar image

1★vicky002 ♦♦
2561314


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

link

answered 29 Mar '15, 14:13

kevind's gravatar image

1★kevind
1482312
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) amanjain1108934★

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?

link

answered 29 Mar '15, 14:25

tinchy_stryder's gravatar image

6★tinchy_stryder
8114
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) dpraveen ♦♦4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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