May 24, 2021 2021 TCO Algorithm Round 2A Editorials

RPSMagicTrick

The problem statement is a faithful description of an actual (very old and quite basic) magic trick. The author of the problem encountered this trick in an old book by the magician Robert E. Neale. The core of the problem was to understand how the magician can do what he does, and then to do the same.

As with any good magic trick, there are many bells and whistles to confuse you: pedestals, statues, weapons, and a lot of banter done by the magician. They all serve the same purpose: to hide how simple the situation actually is.

At the beginning the volunteer places the goddesses onto the pedestals and gives them weapons. From this point on, there will always be a cycle of three goddesses: the one with rock beats the one with scissors, the one with scissors beats the one with paper, and the one with paper beats the one with rock.

There are only two possible cyclic orders of goddesses: ABC and ACB. Thus, we have one of two situations: either (A beats B, B beats C, C beats A) or (A beats C, C beats B, B beats A).

The magician now uses the setup phase to discover which of these situations is the actual one: he makes a guess and he has the volunteer verify that guess.

From this moment on, each swap changes the cyclic order into the opposite one. Try it out:

• If you swap any two statues, the order reverses. (If X beats Y and you swap them, now Y beats X because the weapons remained in place. X now has the weapon that beats Z’s weapon, and Y now has the weapon that is beaten by Z’s weapon.)
• If you swap any two weapons, the order also reverses. (Same analysis as above.)

Thus, hearing the type of the swap is not necessary at all — the task would still be solvable if all ‘S’ and ‘W’ were changed into ‘-’s. The magician just remembers the current cyclic order, and each time the volunteer makes a swap, the magician reverses the order in his head.

The 80 percent accuracy was another of the tricks the magician used to deceive you. Knowing what we know now, the magician can clearly always give a correct “prediction”. And so can your program, if you do the same.

Probably the simplest implementation looks as follows:

• Initially, the guess you want to make is your example guess.
• If the volunteer answered “Wrong.”, you reverse your guess.
• Each time the volunteer makes a swap, you reverse your guess.
• Each time the volunteer asks a question, you announce your current guess.

TheUltimatePackages

We are given a DAG: a directed acyclic graph of package dependencies.

Let’s divide the DAG into layers as follows: Layer 0 are all packages with no dependences. Remove layer 0 from the graph. Layer 1 are all packages that now have no dependences left. And so on. We can easily compute the layer of each package in O(n+d) time during a standard topological sort of the graph. We will use L(X) to denote the layer of package X.

We will say that two packages are comparable if one needs the other, and that they are incomparable if they don’t. If two packages are incomparable, neither of them is an ultimate package.

Whenever two packages ended in the same layer, they are clearly incomparable. This gives us a necessary condition: a package can be an ultimate package only if it is alone in its layer. We will call such packages candidates.

This necessary condition is not sufficient yet, but we only need one more observation.

Let X be a candidate for an ultimate package. Each package in a layer greater than 0 depends on some package in the previous layer, and that implies that all packages in layers greater than L(X) need X.

Thus, the only thing that can stop X from being ultimate is a package Y such that Y is in a layer smaller than L(X), and X does not need Y.

Let’s add a second necessary condition as follows:

For each package Y:

• if no packages depend on Y, packages in layers below L(Y) cannot be ultimate packages.
• If packages Z1, … , Zk depend on Y, let UB = min( L(Zi) ). Then, packages in layers strictly between L(Y) and UB cannot be ultimate packages.

In both cases, this is because each package within those layers is clearly incomparable with Y. (They are below Y so Y does not need them, and all direct dependency links from Y go below those packages, so those packages do not need Y.)

Together, the two necessary conditions are also sufficient. In order to show this, we need to show that for each candidate X that is not an ultimate package, some package Y will eliminate it.

Let X be a candidate that is not an ultimate package. Among all packages incomparable with X, let Y be one with the largest layer number. What can we tell about this particular Y? Either there are no packages that depend on Y, or each package that depends on Y is below X (otherwise that package would be an even deeper option for Y.) Thus, this particular Y will eliminate X.

We can eliminate all candidates that aren’t ultimate packages in O(n+d) time: for each package Y we construct one forbidden interval and then we sweep through all those intervals to find out which layers have been banned.

TwoPolarStations

This is a combinatorics problem: we are supposed to count the number of spanning trees of the given graph. For smaller inputs it would be solvable via Kirchhoff’s Matrix Tree theorem. (The number of spanning trees of any undirected graph can be computed in polynomial time as a determinant of a suitable matrix.) In this problem, this gives us a quick and easy way to get the correct answers for small tests – still useful for testing and debugging (and OEIS lookup for simpler graph classes). As you are doing this locally, you can use libraries such as numpy.linalg for easy implementation.

But back to the original problem. Let’s start by defining some standard graph classes:

The wheel of size N is a graph with N+1 vertices: a cycle of length N and a central vertex connected to all N vertices on a cycle. Let W(N) be the number of spanning trees of a wheel.

The fan of size N is a wheel of size N without one of the cycle edges. In other words, the central vertex is now connected to all N vertices of a path. Let F(N) be the number of spanning trees of a fan.

For N > 1 let’s call the two endpoints of the fan’s path the ends of the fan. Let T(N) be the number of ways to make a spanning forest of a fan with exactly two components and each end of the fan in another component.

All spanning trees of the given graph can be divided into two disjoint sets: those where we do connect the two habitats and those where we don’t.

If we do connect the two habitats, we can now consider them a single vertex. This changes the input graph into a wheel and thus gives us W(N) spanning trees.

If we do not connect the two habitats, we are left with two fans (of sizes A = hi-lo+1 and B = N-A) with ends connected by two edges. If A=0 or B=0, there are no such spanning trees. Otherwise we proceed as follows:

Look at the two edges that connect the two fans. We cannot discard both of them. Let’s look at the possible cases:

• If we take one of them, we have two ways to choose which one. Then, regardless of the choice, we need to make a spanning tree in each of the fans separately. Thus, we get 2*F(A)*F(B) spanning trees.
• If we take both of them, we have to make a spanning tree from one fan and a spanning forest (of the type described above) from the other fan. This gives us the last T(A)*F(B) + F(A)*T(B) spanning trees.

All that remains is to find a quick way to compute W, F and N.

W and F are simple standard sequences closely related to the Fibonacci sequence, the easiest way to find a recurrence they satisfy is to determine some small values and look them up in OEIS. For completeness, below we derive them from scratch.

When computing T we can note that one of the components is always a path of some length K along the path of the fan and the other component is a spanning tree of a fan of size N-K. As we have two ends from which the path can start, we get that T(N) = 2*(F(1) + F(2) + … + F(N-1)). Once we have a recurrence for F, we can easily modify it to a recurrence for T.

Spanning trees in a fan
Let C be the center of the fan and let A be one of its ends.

Lemma: The number of spanning trees in which A and C are not connected is F(N-1).

Proof: Each spanning tree is a spanning tree of the fan without A + an edge from A to its neighbor on the path.

Corollary: The number of spanning trees in which A and C are connected is F(N) – F(N-1).

Theorem: The values F(N) satisfy the recurrence F(N) = 3F(N-1) – F(N-2).

Proof: Consider the edges from A. If only one of them is in the spanning tree (two options which), the rest of the spanning tree is a spanning tree of a fan of size N-1. This gives us 2F(N-1) options.

In the remaining case the spanning tree contains both edges from A. Let B be the neighbor of A on the path. The edge BC is not in the spanning tree. Suppose we remove the edges AB and AC and instead add the edge BC. This is clearly a bijection between the spanning trees we are trying to count and the spanning trees of a fan of size N-1 in which the center and one specific end are connected. From the lemma we know that there are F(N-1) – F(N-2) of them.

From the recurrence we now know that we can compute F by taking the N-th power of the matrix MF = {{0,-1},{1,3}}: note that (x,y) * MF = (y,3y-x) and thus (F(N-2), F(N-1)) * MF = (F(N-1), F(N)).

The sequence T of partial sums of F can now be computed by taking the N-th power of the matrix MT = {{0,-1,0},{1,3,2},{0,0,1}}. As T(N) = 2*F(N-1) + T(N-1), this matrix satisfies (F(N-2), F(N-1), T(N-1)) * MT = (F(N-1), F(N), T(N)).

(Coincidentally, F(N) is the 2N-th Fibonacci number.)

Spanning trees in a wheel
See the following paper: http://www.m-hikari.com/ams/ams-password-2009/ams-password45-48-2009/shirdarehAMS45-48-2009.pdf

(A nice derivation of the recurrence with pictures. Also has the formula for fans.)