PROBLEM LINKPanel MembersProblem Setter: Sergey Nagin DIFFICULTY:Hard PREREQUISITES:Dynamic Programming, Tree, Memoization, Mathematics. PROBLEM:A tree is an undirected graph on $N$ vertices with $N1$ 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)$. EXPLANATIONIt 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 $size1$ children of root node. i.e How to calculate $F(A)$ ? $F(A)$ is itself dependent on function. $F(A)$ can be calculated as follows: i.e 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. COMPLEXITYExponential Time AUTHOR'S AND TESTER'S SOLUTIONS:The author's solution can be found here. SIMILAR PROBLEMasked 27 Nov '15, 19:02
