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

×

COPR16B : Editorial

PROBLEM LINK:

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

DIFFICULTY:

MEDIUM

PREREQUISITES:

BFS/DFS, Combinatorics, Multinomial Theorem

PROBLEM:

Find the number of ways to connect the k clusters of a graph when k>=2 using minimum number of edges, else print "Everyone is connected".

EXPLANATION:

First of all the minimum of number of edges to be used is (k-1), where k is the number of components in the graph, which can be found easily using BFS/DFS.

Now, notice that if you consider the k components as vertices, then if you add the k−1 edges to make the graph connected you actually get a tree of k vertices. So every tree on k vertices generates a set of ways to connect the graph. Label the components by $1, 2 \cdots, k$ and their sizes by $a_1,a_2, \cdots, a_k$. If T is on the set of vertices ${1,2⋯,k}$, then the number of ways of connecting an edges $(i,j) \in E(T)$ is $n_{i,j} = a_i.a_j$.

Thus, the number of ways of connecting the components using T is $\Pi_{(i,j) \in E(T)} n_{i,j} = \Pi_{i=1}^{k} a_{i}^{d_i}$ where $d_i$ is the degree of vertex i in the tree T.

So, the number of ways of connecting the components is

$\sum_{T \ tree \ of \ K_k} \Pi_{i=1}^{k} a_{i}^{d_i} = \sum_{\sum_{i=1}^{n} d_i=2(k−1)} N(d_1,d_2,\cdots,d_k) \Pi_{i=1}^{k} a_{i}^{d_i}$, where $N(d_1,d_2,\cdots,d_k)$ is the number of labelled trees on k vertices and labelled vertex i has degree $d_i$.

We have $N(d_1,d_2,\cdots,d_k) = \frac{(k−2)!}{\Pi_{i=1}^{k} (d_i−1)!}$. See here for more info.

So, $\sum_{T \ tree \ of \ K_k} \Pi_{i=1}^{k} a_{i}^{d_i} = \sum_{\sum_{i=1}^{n} d_i=2(k−1)} {(k−2)!} {\Pi_{i=1}^{k} \frac{a_{i}^{d_i}}{(d_i−1)!}} $

$= (\Pi_{i=1}^{k} {a_i}) \sum_{\sum_{i=1}^{n} {(d_i-1)=k-2}} {(k-2)!} \Pi_{i=1}^{k} {\frac{a_{i}^{d_i}}{(d_i-1)!}}$

$=(\Pi_{i=1}^{k} {a_i}){(\sum_{i=1}^{k} {a_i})}^{k-2}$ (by multinomial expansion theorem).

Therefore the number of ways required are $=(\Pi_{i=1}^{k} {a_i}){(\sum_{i=1}^{k} {a_i})}^{k-2}$ = ${n}^{k-2}(\Pi_{i==1}^{k} {a_i})$, since $\sum_{i=1}^{k} {a_i} = n$, where n = total number of vertices.

Now, to implement the above algorithm, just run bfs on the graph. For each connected component found, find the number of vertices in it and multiply the answer by that number. In the end multiply the final answer by ${n}^{k-2}$. If k=1, print "Everyone is connected", else print the required answer

COMPLEXITY

O(n + m), n = number of nodes in graph, m = number of edges in graph

AUTHOR'S SOLUTION:

Author's solution can be found here.

asked 26 Mar '16, 02:14

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 29 Mar '16, 16:17

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×15,852
×2,658
×593
×32
×1

question asked: 26 Mar '16, 02:14

question was seen: 554 times

last updated: 29 Mar '16, 16:17