PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
CodeChef contests are always great for learning and competing. A set of 5 algorithm problems of different difficulty levels, a challenge problem for separating those who solved the same number of problems. The thing which seems to be a bit odd about this is that the winner is always determined by the challenge problem, as most top coders are able to solve a set of any 5 problems given 10 days. I tried to set a couple of really hard problems this month for a change. And yes – there were only 10 accepted solutions to them in total, so my goal was achieved 
Anyway, it won’t probably be a trend – such hard problems are always difficult to come up with.
Let’s move on to the solution. For a start, let f(N,M) be the number of hypertrees on N vertices and M edges.
Suppose we’ve fixed a particular edge of a hypertree. What will happen if we remove it? The correct answer is: the hypertree will break down into two or three components. The rest of the solution may seem easy. We can try every possible way of distribution of the vertices between (or among) the components and also every possible way of distribution of edges. So, if we’ve got a way to break it down into components (this means (vertices, edges)) (N1,M1), (N2,M2), (N3,M3) such that N1+N2+N3 = N and M1+M2+M3 = M, then do the following: f(N,M) += f(N1,M1) * f(N2,M2) * f(N3,M3). The same applies when there are only two components. As we try every possible starting edge, we should finally divide f(N,M) by M.
To see why this is wrong, consider an example. Suppose there are just 5 vertices. First, we take an edge (1,2,3) to separate the hypertree into components (1,2,4,5) and (3). Then, in (1,2,4,5) component we take an edge (1,2,4) to separate the hypertree into components (1) and (2,4,5). Then, in (2,4,5) component we finally take an edge (2,4,5) to separate the hypertree into components (2), (4) and (5). Everything seems correct, but… notice that (1,2,4) can actually be removed! This happened because after (1,2,3) separated the hypertree into (1,2,4,5) and (3), vertices 1 and 2 remained connected through an already processed edge, and we should have remembered about that, as edge (1,2,4) couldn’t just separate (1) from (2,4,5) now.
In general, if we look at the connected pairs induced by the processed edges, they’ll form some connected components of vertices which we’ll call bunches (not to mix them up with the components of the hypertree). As the actual indices of the vertices don’t matter, it’ll be enough if we just have a set (or, in fact, multiset) of sizes of the bunches. The recurrence turns into f(A,M), where A is the aforementioned set. The starting set is thus (1,1,…,1) (consisting of N 1’s). In the example above, the starting set is (1,1,1,1,1), and after the first edge it becomes (2,1,1).
These induced connections, of course, bring some problems to deal with. The easy case now is when removing an edge results in just two components. There should be no edges between the components (so every bunch should go to either side as a whole), otherwise the initial edge can be removed. If the two vertices of the initial edge which go to the same component are from different bunches, these bunches should become connected now. We can find the answer recursively for the resulting sets and then merge these answers to recalculate our DP.
When removing an edge results in three components, some induced connections may be split between the components. Still all three components shouldn’t be connected by them, otherwise the initial edge can be removed again. Then, we should connect all bunches if they are connected by the initial edge. Even more, before starting to search for the answer for the first component, we should connect all the bunches from the second and the third component (and similarly for the other components) – otherwise it may so happen that a pair of bunches becomes connected in both the first and the second components, so an edge in either of them can be removed. Only after all these things, we can finally move on to the smaller sets
This part should also be optimized, as 3^17 * 17^4 is a bit too much (of course it’s not too much in case you have a lot of time). The key is to notice that the bunches of the same size are indistinguishable, so we don’t need to try every possible distribution of them. My solution which has this optimization works for about a minute for N = 17 and it works for several hours without it. It should probably work even faster if the distributions are generated using recursion.
Note that a more understandable edition of my code has been uploaded
David Stolp, who was the tester this time, used a different approach (in my opinion, it’s even simpler to understand). Here is his description:
I define a biconnected hypertree as one with no articulation points. Then I define biconnected components in the usual fashion. My algorithm has 2 stages. First I count the number of biconnected hypertrees (this is rather slow), then use those values to compute the total number of hypertrees (this is quite fast).
Consider a biconnected hypertree. Consider any edge of this hypertree, and count the number of hyperedges each of its 3 vertices belongs to. How many of the vertices belong to exactly 1 hyperedge? It can’t be 0 because then it wouldn’t be a hypertee. It can’t be 2 because then it wouldn’t be biconnected. If it’s 3, then the hypertree consists of only a single hyperedge. That leaves 1.
Now remove from each hyperedge the vertex that appears only once. This turns the hypergraph into a plain graph, and this graph must be biconnected. Thus, my first step is to count the number of biconnected graphs with n vertices and m edges for n+m<=17. This is where most of my execution time is because I don’t bother to memoize. Some combinatorics gets me the total number of biconnected hypertrees. Then I brute force all configurations of biconnected components in a hypertree (using memoization this time to speed things up).
David’s solution actually works several times faster than mine. It also made me believe that the problem was easier than I had previously thought, but it still proved to be very hard
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.