December 2011 Contest Problem Editorials

Problem Tester for the December 2011 Contest was David Stolp.

-------------------------------------------------------------------------------------------------------

MOVES (written by AnhDQ)

Suppose that the robot always takes the "right" move at first. We could easily see that a way of robot reaching cell (N, N) is just a set of cells in which the robot takes "turns". This set is chosen by selecting a combination of K/2 column indices and (K-1)/2 row indices among N-2 indices each dimension. It is easily computed by formula C(K/2, N-2) * C((K-1)/2, N-2). At last, we double the result of this formula to get the last result (because the table is a square one so it is totally the same in case the robot takes the "down" move at first).

The last problem is compute the Combination formula as fast as possible. In this case we have to compute the result modulo 1,000,000,007 which is a prime, so we just use a power function to fast compute that (in logarithmic time).

You can view the solution here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

STREGGS (written by Hiroto Sekido)

You can view the editorial for this problem here.

You can view the solution here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

CHEFGIFT (written by Vamsi Kavala)

You can view the editorial for this problem here.

You can view the solutions here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

SPIN (written by Gennady Korotkevich)

The easiest way to get accepted is to output a sequence of 100 random moves for N = 2 and -1 for all other cases. Not that it really matters :)

One of the simplest good approaches is the following. Let's fix color C into which we're going to color all the wheels. Let's say that a wheel is reachable from C if it can be colored into C through a sequence of moves each of which rotates a wheel of color C. It's easy to check this for all wheels in O(NM) total time. Let's rotate some random wheel from those which are not reachable from C several times until all of the wheels are reachable. When this finally happens, let's rotate some random wheel of color C so that at least one of the wheels is colored into C at the first iteration. It can be seen that we'll actually color all the wheels into C pretty quickly. This approach is enough to get a score of under 450.

Other solutions should probably use a similar idea. Tiancheng Lou's solution receiving a score of under 303 also makes use of beam search, as it can be inferred from his code.

You can view the solution here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

SHORT2 (written by Gennady Korotkevich)

You can view the editorials for this problem here.

You can view the solutions here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

HYPER (written by Gennady Korotkevich)

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

You can view the solutions here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------