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

×

SEATR - Editorial

PROBLEM LINK

Practice
Contest

Panel Members

Problem Setter: Sergey Nagin
Problem Tester: Istvan Nagy
Editorialist: Sunny Aggarwal
Contest Admin: Praveen Dhinwa
Russian Translator: Sergey Nagin
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

DIFFICULTY:

Hard

PREREQUISITES:

Dynamic Programming, Tree, Memoization, Mathematics.

PROBLEM:

A tree is an undirected graph on $N$ vertices with $N-1$ edges and no cycles. Let just consider a peculiar way of comparing two trees. To describe it, let's start with the way, we have stored a tree. For every tree $T$, we has a value $V$ — the root of the tree, and for every vertex $i$, we have an ordered list $Q_i$ with $L_i$ elements — $Q_{i, 1}, Q_{i, 2}, ..., Q_{i,L_i}$ which are children of the vertex $i$. We assume that the two trees will be equal if their roots are the same and for every $i$, the ordered list $Q_i$ is the same in both the trees.

Consider the given tree $T_1$ $[V=1, Q_1=[2, 3], Q_2=[], Q_3=[]]$ and $T_2$ given as $[V=1, Q_1=[3, 2], Q_2=[]$$, Q_3=[]]$, they will be considered different because $Q_1$ in the first tree is not equal to $Q_1$ in the second tree.

Let us consider that the $E_i$ denotes the number of vertices adjacent to vertex $i$. Given an array $C$ of $N$ elements, Let $f(C)$ be the number of different trees such that there exists a permutation $P_1, P_2, ... , P_N$ so that $E_{P_1} = C_1, $$E_{P_2}= C_2, ... , E_{P_N} = C_N$. We are provided with array $C$ and asked to compute the number $f(C)$ modulo 1000000007 $(10^9+7)$.

EXPLANATION

It is easy to notice that if $1$ permutation satisfies a configuration of the tree then every possible permutation will satisfy same configuration. So, we will first compute the number of different trees possible for a given permutation say 1, 2, 3, .... N and then will multiply this answer with N!.

Let us consider some notation to understand the solution better. Let us consider a function $F(A)$ denotes the number of different trees possible when there are exactly $A_i$ nodes in each tree with $i$ adjacent nodes. Let us consider another function $G(size, A)$ denotes the number of different tree possible when there are exactly $A_i$ nodes in each tree with $i$ adjacent nodes but each tree root has exactly $size$ number of adjacent nodes.

How to calculate $G(size, A)$ ?

$G(size, A)$ denotes the number of different trees possible (say $T$) when there are exactly $A_i$ nodes in each tree with $i$ adjacent nodes but each tree root ( say $R$) has exactly $size$ number of adjacent nodes. We can compute $G(size, A)$ by choosing a subset of $A$ (say $Z$) and can assign the chosen subset to the first child of root node $R$ and can distribute the remaining set of nodes over the remaining $size-1$ children of root node.

i.e
$$G(size, A) = \sum_{\substack{ Z \subset A }}{F(Z) * G(size-1, A-Z)}$$

How to calculate $F(A)$ ?

$F(A)$ is itself dependent on function. $F(A)$ can be calculated as follows:

i.e
$$F(A) = \sum_{ if (A_i \gt 0) }{G(i, X)}$$

where $X$ = updated $A$ with $X_i = A_i - 1$ as we have selected $1$ node with $i$ adjacent nodes as root.

NOTE: We have received linear time solutions for this problem during the contest. So, Please have a look on them. This is an overview of author's approach. I am still not very much clear with the idea so any suggestions and contributions to this post is welcome.

Please have a look at author's solution to learn more about the discussed solution.

COMPLEXITY

Exponential Time

AUTHOR'S AND TESTER'S SOLUTIONS:

The author's solution can be found here.
The tester's solution can be found here.

SIMILAR PROBLEM

Codechef Problem DEVVOTE

asked 27 Nov '15, 19:02

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

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,212
×711
×139
×107
×95

question asked: 27 Nov '15, 19:02

question was seen: 625 times

last updated: 27 Nov '15, 19:02