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


SEATR - Editorial



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




Dynamic Programming, Tree, Memoization, Mathematics.


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)$.


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.

$$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:

$$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.


Exponential Time


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


Codechef Problem DEVVOTE

asked 27 Nov '15, 19:02

ma5termind's gravatar image

accept rate: 11%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 27 Nov '15, 19:02

question was seen: 625 times

last updated: 27 Nov '15, 19:02