-is-this-fft-'s blog

By -is-this-fft-, 3 months ago, In English

Someone posted a modified variant of ABC 180 F here before and asked for help solving it. The task went as follows: given $$$n$$$ and $$$\ell$$$, count the number of labeled graphs on $$$n$$$ vertices such that no vertex has a degree exceeding 3, there is no cycle in any connected component (i.e. the graph is a forest) and the largest connected component has exactly $$$\ell$$$ vertices.

I wrote a rather long comment explaining how to solve it. I hit "post" and...

the blog was gone.

To whoever was the author: please don't do this. It's very frustrating to put effort into writing an explanation only to discover that it had been completely in vain. Even if you already got an answer from elsewhere, other users might enjoy reading the solution. It was not the case here, but especially don't delete/hide your blog if there already are answers in the comments. This way you're effectively just erasing other people's work. That sort of thing can really put me and others off from helping people in the comments altogether.

So that my effort wouldn't be completely wasted, I decided to post the contents of my comment here as a separate blog. (In theory, this might have been some ongoing contest or interview problem. But it really is an obvious modification to the AtCoder problem and I sort of believe the author. Besides, all of this is rather standard.)


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$$$. Let's call this value $$$f(k)$$$.

Now to the original problem. I'm going to change it slightly and say we instead need to find the answer where the largest connected component can be up to $$$\ell$$$. This doesn't really change anything as you can calculate the answer for "up to $$$\ell$$$" and then from it subtract the answer for "up to $$$\ell - 1$$$".

Let $$$\mathrm{dp}[i]$$$ be the number of forests with $$$i$$$ vertices where the largest connected component has size up to $$$\ell$$$ and every degree is up to 3. Suppose we have such a forest. We are now going to add to it another tree with $$$k$$$ vertices. There are $$$f(k)$$$ ways to choose a tree. But how many ways are there to add this new tree to the forest? Keep in mind that the indices for this new tree can be "interleaved" with the old forest. E.g. vertices 1 and 3 could be in the old forest and vertices 2 and 4 in the new one. To avoid double-counting, we will assume that the vertex with index $$$i + k$$$ belongs to the new tree. Among the other $$$i + k - 1$$$ vertices, we choose $$$i$$$ of them to assign to the old forest and $$$k - 1$$$ to assign to the new. Therefore, $$$\mathrm{dp}[i]$$$ contributes $$$f(k) \binom{k + i - 1}{i}$$$ times to $$$\mathrm{dp}[i + k]$$$.

In total, the complexity will be $$$O(n\ell)$$$.

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

»
3 months ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

Uhh, I am the author for the blog and I appreciate your help. I didnt delete the blog, it might be a bug from codeforces(when you commented at the same time as I edited the blog).

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +50 Vote: I do not like it

    As you can see, it's still in my blogs section. Link is here: https://codeforces.com/blog/entry/123189

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

    OK, I understand what happened — you probably hit "save draft"? This might be counterintuitive, but it removes the blog from public view (and is only visible to you as a draft) until you hit "post" again.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      Oh yeah I did, I changed the blog a little bit while I was eating breakfast and thought saving draft just adds a copy on the old one. Maybe that was the problem, i didnt know it would be hidden for the public. Nevertheless, thx for answering.

      Btw for anyone who is concerned: k=1 is a corner case.

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

It is also not an ongoing contest problem, just chilling out here. But do you think the problem was nice?

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

why are you using discord light mode sir