Editorial for Appleby Contest '20 P5 - Ridiculous Tree

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Let's begin by trying to find a DP solution to this problem:

We can define the DP state as follows:

Let $dp[i]$ ~dp[i]~ be the number of permutations of the nodes in the subtree of node $i$ ~i~ that satisfies the property Ridiculous Ray wants.

From this state, we can get the following recurrence:

Let $s_1, s_2, \dots, s_k$ ~s_1, s_2, \dots, s_k~ be the set of nodes adjacent to node $i$ ~i~.

Let $sz[i]$ ~sz[i]~ be the number of nodes in the subtree of node $i$ ~i~.

$\displaystyle dp[i] = (sz[i]-1)! \cdot \prod_{i=0}^k \frac{dp[s_i]}{sz[s_i]!}$

Observation: the resulting formula we get from expanding this recurrence on any tree will be a sequence of multiplications. Instead of storing the prime factorization of the overall answer, we can just count the number of times each integer occurs in the product and add its prime factorization $f$ ~f~ times to the answer (where $f$ ~f~ is its frequency).

Then, to optimize the solution to get full points, a difference array can be used as the answer is the product of $\mathcal O(N)$ ~\mathcal O(N)~ factorials.

The first subtask was meant to reward brute force solutions.

The second subtask was meant to reward contestants that found the recurrence but computed the DP values directly, either by storing the prime factorization as a map data structure or by using arbitrary precision integers.

Time complexity: $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~

Comments

17

ecnerwal commented on Feb. 16, 2021, 6:13 a.m. ← edited →

A simpler formula: then answer is $\displaystyle n! \prod_{i=1}^{n} \frac{1}{sz[i]}$ A proof: we'll calculate the probability that each constraint is satisfied. Then, each node has an $1/sz[i]$ ~1/sz[i]~ probability of being the smallest node in its subtree, and furthermore these probabilities are independent. Thus, the number of good assignments (such that all nodes are smaller than their children) is exactly $n!$ ~n!~ times the product of these probabilities.

9

Plasmatic commented on Feb. 16, 2021, 3:59 p.m.

:O very cool