NeoYL's blog

By NeoYL, 3 months ago, In English

Below is a variant of the problem:

Link

Given that there are $$$N$$$ ($$$1 \leq N \leq 300$$$) nodes.

An integer $$$L$$$ ($$$L \leq N$$$) is also given.

Find the number of ways to construct a graph with the following properties:

  1. The graph is a forest

  2. The largest connected component's size = L

  3. All nodes have degree $$$\leq 3$$$

  4. There isn't any repeated edge

Credits to -is-this-fft-, for the amazing cost function in the comments section. And his blog here: https://codeforces.com/blog/entry/123211

The solution is pretty cool and leave a like for him too!

Solution

Note: I won't delete a blog that has contents that might act as a learning material for anyone.

  • Vote: I like it
  • +42
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please leave a like if you loved the idea of the problem!

»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I didn't really read most of what you wrote but here is how I'd solve this.

Let's first learn to count the number of labeled trees with $$$k$$$ vertices where each vertex has degree at most 3. We'll use Prüfer sequences. A Prüfer sequence of a tree with $$$k$$$ vertices is an array consisting of $$$k-2$$$ entries. Importantly, each tree corresponds to exactly one sequence and vice versa. Also, every vertex $$$u$$$ appears in the sequence exactly $$$\mathrm{deg}(u) - 1$$$ times.

So we need to count the number of arrays consisting of $$$k - 2$$$ entries such that every vertex appears in the array 0, 1 or 2 times. We will do that with DP: let $$$\mathrm{dp}[i][j]$$$ be the number of sequences where we have already placed the first $$$i$$$ vertices that have length $$$j$$$ now. We'll try to place the $$$i$$$-th vertex now. A sequence of $$$j$$$ elements has $$$j + 1$$$ "slots" where we could insert the instances of the $$$i$$$-th vertex. So,

  • $$$\mathrm{dp}[i][j]$$$ contributes once to $$$\mathrm{dp}[i + 1][j]$$$;
  • $$$(j + 1)$$$ times to $$$\mathrm{dp}[i + 1][j + 1]$$$;
  • $$$\binom{j + 1}{2}$$$ times to $$$\mathrm{dp}[i + 1][j + 2]$$$.

You can calculate this DP in $$$O(n^2)$$$ time and you'll be interested in the value of $$$\mathrm{dp}[k][k - 2]$$$ for every $$$k$$$. And given what you wrote above, I believe you can take it from here.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Woah, that's cool I didn't really think deep for dp on prufer sequence. Thx for answering. Also I believe that k=1 is a corner case. My blog was long just because I wanted to show some of my ideas, which might be useful for others.