SEATR - Editorial

ma5termind · November 27, 2015, 7:03pm

PROBLEM LINK

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.