# Solutions to the USC Spring 2018 Code-a-Thon

It isn't necessary to have read CLRS cover-to-cover to be able to compete in Code-a-Thons, although owning a copy certainly helps. Many of this year's problems were conceived while flipping through these pages, thinking up back stories for questions whose solutions were in pseudocode in front of me. I wrote one fewer question than I had intended to this semester, although only two out of the 71 participants in the upper division were able to complete the problem set, so it would seem the overall competition difficulty was ideal. With one finisher clocking in at just under nine hours (wow!) and the other at just over 23 hours (although analysis of submission times indicates a much deserved sleeping break), the competition provided a difficult challenge that was not insurmountable for our quick witted competitors. I am extremely satisfied with the performance of this semester's participants, and I thank the USC ACM chapter for their efforts in organizing the event, and to the University of South Carolina and Krumware for their support.

Before we go over the solutions, I will outline the format of the competition. Participants had 24 hours to solve a series of programming challenges. Code-a-Thons are distinctly different from Hack-a-Thons, and are much more akin to programming math competitions. There are several high-profile contests of this nature, including Google Code Jam and ACM's ICPC. The USC Code-a-Thon is split up into 4 divisons, which roughly correspond to 1st semester CS students, 2nd semester CS students, 3rd semester CS students, and 4th (and up) semester CS students. "And up" in the highest division refers to upperclassmen, as well as graduate students. As it would make little sense to expect a first semester freshman to be able to complete the same difficulty challenges as a graduate student, we further divide the divisions into an upper and lower division. Lower division problems often deal with elementary data structures (stacks for example) or with basic algorithms (like binary search). Upper divison problems deal with advanced topics in computer science, including algorithmic design, combinatorics, graph theory, and more. The difficulty gap between these two divisions is quite large. We use Hackerrank to host our competitions, and you can see the problems in their original format by following the links below. If you are interested in these types of problems, I encourage you to visit the problems and attempt them yourself, or to at least ponder their solutions before looking at the ones provided below. Hackerrank allows you to submit code in a variety of languages, and will automatically test your program on a variety of test cases provided by the problem author.

Links to blank contests (best for following along or trying for yourself):

The Github repositories for each division have been made public as well. These contain solutions (sometimes in multiple languages or with multiple approaches), test cases, test case generators, and misc. notes or extra information.

## Solutions

I will refrain from going over the solutions to the lower division problems, as most of them have fairly straightforward solutions. If there is interest, I may add these solutions at a later date. In the mean time, here are the solutions to the upper division problem set. These are organized in the order in which the problems appeared to contestents, and are approximately in increasing order of difficulty.

#### Problem 1: Leonhard's Libations

Every semester we try to include a trick question where the problem appears to be a programming problem, but the programming solution is incredibly difficult or time-consuming. The best example of one such trick problem required nothing more than knowledge of the four color theorem and 7 characters of Python 2: print 4.

This problem is not quite as elegant as that one, but it got the job done.

Several of the mathematically inclined participants immediately recognized the formula in the problem description:

$$\sum_{i=0}^{n} \frac{1}{i!}$$

which converges to $e$ when $n = \infty$.

The question asks the programmer to output the value of this formula for various values of $n$ (with $1 \leq n \leq 2^{2^{2^{2^{2} } } }$), rounded to six decimal places. The upper bound for $n$ is a 19729 digit decimal number, which gives a hint that performing any real computation with $n$ is infeasible. Let's look at a table of corresponding values of $n$ and $f(n)$ (which is $n$ applied to the formula above):

$n$ $f(n)$
$1$ $2$
$2$ $2.5$
$3$ $2.\overline{6}$
$4$ $2.708\overline{3}$
$5$ $2.71\overline{6}$
$6$ $2.7180\overline{5}$
$7$ $2.71825396825397$
$8$ $2.71827876984127$
$9$ $2.71828152557319$
$10$ $2.718281801146384$
$11$ $2.718281826198493$
$12$ $2.718281828286169$

Okay, and now let's look at the same table with $f(n)$ rounded to six decimal places:

$n$ $f(n)$
$1$ $2.000000$
$2$ $2.500000$
$3$ $2.666667$
$4$ $2.708333$
$5$ $2.716667$
$6$ $2.718056$
$7$ $2.718254$
$8$ $2.718279$
$9$ $2.718282$
$10$ $2.718282$
$11$ $2.718282$
$12$ $2.718282$

Aha! a pattern emerges. As $n$ tends to infinity, $f(n)$ converges to $e$, and with $n > 8$, our approximation of $e$ does not get any better when we limit it to only six decimal places. Since we have only nine possible cases, we can provide a solution to this problem without using any sort math at runtime. In Python 3, this solution might look like this:

line = input()

n = -1
if len(line) == 1:
n = line

if n == '1':
print("2.000000")
elif n == '2':
print("2.500000")
elif n == '3':
print("2.666667")
elif n == '4':
print("2.708333")
elif n == '5':
print("2.716667")
elif n == '6':
print("2.718056")
elif n == '7':
print("2.718254")
elif n == '8':
print("2.718279")
else:
# Beyond n = 9, n converges to the mathematical constant e for 6 decimal
# places.
print("2.718282")


There were several (subtle) hints to the solution in the problem text. The problem name, "Leonhard's Libations", is a reference to Leonhard Euler, the mathematician for which $e$ is named. Additionally, the sentence, "On any given day, Leonhard knows his limits," (and the many other references to limits) was to indicate that perhaps the limit of the proposed formula should be considered. We had 33 students solve this successfully. Even more recognized that the formula converged to $e$, but they couldn't quite figure out how to express this in code.

#### Problem 2: Pineapple Pack

This problem was the only problem of the hard problem set that I did not write. For an entirely unrelated reason, this was also the problem with which we had the most trouble. I tend to use Python for Code-a-Thons for its concise syntax, expressiveness, and arbitrary precision arithmetic. Not having to worry about integer overflow (or the verbosity of BigInteger) is a huge boon. I haven't used Python for many floating point programs, since the Code-a-Thon problems I author tend to avoid floating point altogether; using string comparison to check solutions falls short for floating point output when you allow participants to submit code in a variety of programming languages.

My naïveté and crunch-time-coding led me to assume that Python would provide arbitrary precision arithmetic for non-integral calculations out of the box. It does not (one must use the decimal module). More specifically, I assumed that x // y was equivalent to int(x / y) (in Python, // is the integer divison operator. This operator has equivalent functionality to most other language's divison operators; thanks PEP 238). Try executing the following line in a Python REPL:

int(9007199254740993 / 1) == 9007199254740993 // 1


You will be met with the output False. The number in that example is actually the smallest positive integer $x$ where the above statement is False. This is because double precision floating point specifies 53 bits of significand precision. Since $9007199254740993 = 2^{53}+1$, it is not guaranteed to be able to be accurately represented as a floating point number (although $2^{53}+2$ works fine, see the Wikipedia page linked above for the reason why).

Here you came for a solution to a Code-a-Thon and instead you are getting a lecture on IEEE-754. I do apologize for this, but perhaps it will keep you from committing the ultimate Code-a-Thon author's sin: providing incorrect test cases. Fortunately we caught this issue early on, but not before several participants wasted time debugging correct code. This was the only problem that wasn't correct, so I suppose it could have been worse.

Now, how is this problem actually solved?

The problem assumes a completely filled and infinite size ternary tree, where each node is labeled with an index. The labeling scheme is straightforward, with the root node having index 1, the nodes on the next layer having indices 2, 3, 4, and so on. The first three layers of the tree might look something like this:

This problem asks the programmer to write a program that provides a series of directions to navigate from the root node to some node in tree. The index of this destination node is the input to the program. The series of directions should be a string comprised of the characters L, M, and R, corresponding to left, middle, and right. Looking at the tree above, we can see that input 12 should produce output RM. Similarly, input 7 should produce output LR.

It seems that a top down approach is unlikely to work, since the size of the tree grows exponentially with each additional layer. Thus, we must start at the specified node and work our way up. To generalize, we need a way to find out which child (left, middle, or right) that a given node is of its parent. After finding this, we need to find the index of the parent and repeat this process until we get to the root node.

Let's consider a node $i$, where $i$ is the index of the node. How can we find out if $i$ is a left, middle, or right child of its parent? Let's consider the indices of all the left children in the tree above. We have $\{2, 5, 8, 11\}$. What about the middle children? $\{3, 6, 9, 12\}$. And the right children? $\{4, 7, 10, 13\}$. Looking at these three sets we can see a clear pattern. Each right child will have an index one greater than some middle child's index and each left child will have an index one less than some middle child's index. We can also see that each middle child's index is evenly divisible by three. So what would happen if we considered $i \mod 3$? There are three distinct outputs to consider: 0, 1, or 2. If we get 0, we know that $i$ is a middle child of its parent, since all middle children have an index divisible by three. If we get 1 we know that $i$ is a right child since all right children have an index one greater than a middle child's index (so they are some multiple of three plus one). Lastly, if we get 2 we know that $i$ is a left child since all left children have an index two greater than a middle child's index (or one less than a middle child's index, as $-1 \equiv 2 \pmod{3}$)

So now we know how to determine if a node is a left, middle, or right child of its parent. How do we get the index of the parent? Let's consider each node and its middle child in the above image. We have $\{(1, 3), (2, 6), (3, 9), (4, 12)\}$. Each node's middle child has an index exactly three times its own index. To find the index of $i$'s parent, we just have to find the middle child nearest to $i$, take its index, and divide that by three. At this point, we must repeat the process described in the previous paragragh and continue up the tree until we get to the root. At each step up the tree, we record if $i$ was a left, middle, or right child of its parent. When we reach the root node we print out the directions we have recorded in reverse order. We must reverse the order because we recorded the directions from the destination node to the root, but we need to output the directions from the root node to the destination.

There is a single edge case for this problem. The constraints indicate that the input of 1 is a possibility. What should we output in this case? From the context of the problem, it would seem that no directions need to be given to get to this node, since the node with index 1 is the starting node. Sure enough, the expected output for this input is simply the empty string. This was test case 2, and a couple of participants had to put a little bit of extra thought into their solution to account for this edge case.

Let's see some code!

n = int(input())

ans = ""

# While we are not at the root node...
while n > 1:
if n % 3 == 0:
# We have found a middle child
ans += 'M'
n = n // 3
elif n % 3 == 1:
# We have found a right child.
ans += 'R'
# The parent node is the middle child's index divided by three
n = (n - 1) // 3
elif n % 3 == 2:
# We have found a left child.
ans += 'L'
# The parent node is the middle child's index divided by three
n = (n + 1) // 3

# Print the directions that we have recorded in reverse
print(''.join(list(reversed(ans))))


We had 30 students correctly solve this problem. Many students skipped straight to this problem since it seemed (and was) more straightforward than the Leonhard's Libations. Many students using C/C++/Java encountered some difficulties because they were using 32-bit integers to read in the input. We carefully chose the input constraint of $2^{63} - 1$ so that the input would fit into an unsigned 64-bit integer. I felt bad watching frustrated students see their (logically correct) code failing on large test cases, but I was once in their position and learning this the hard way kept me from ever making a similar mistake again!

As a Code-a-Thon author, this problem taught me a lot about writing good problems. I should have tested our solution on large (but trivial) test cases. For example, any input of the form $\sum_{i=0}^{h} 3^i$ should simply output a string of $h-1$ Rs, since we have specified the index of a node all the way to the right of the $h$'th layer. When $h=60$, $\sum_{i=0}^{60} 3^i = 63586737412824305271441649801$. Using this as input to our first (and incorrect) solution, we get output:

RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRMLMLLMRMLMRMRRRMMRLLRLRMRLR


Gah! If only we had done more testing. Oh well. We will take this as a lesson learned and be more thorough with our testing next time.

#### Problem 3: Pricey Power

This was the first problem with a difficulty rating of hard. The increase in difficulty was reflected in the number of working solutions. Only five participants solved this problem, all of them in division one.

This problem required less raw ingenuity to solve, and more prior knowledge (or Google-fu). For participants well versed in graph theory, all it took was one glance at the provided image for the first example (see below) to realize this question was about minimum spanning trees. I will frequently use the abbreviation "MST" to refer to minimum spanning trees.

But that's jumping straight to the solution. Let's analyze the problem to figure out exactly what it's asking. SCANA (a real energy company located near Columbia, SC!) has an expensive network of power lines connecting houses in their power grids. Each power line connects exactly two houses to one another, and has an associated monthly cost. This is a perfect problem to model using a graph. The edges between nodes have a numerical value associated with them, so we have a weighted graph. No power line generates money; every power line has a positive cost associated with it. Power can move through lines freely in either direction, so our graph is undirected. We are told in the problem description that there can be multiple power grids in each network, meaning two houses may have no connection between them (i.e. no combination of edges in the graph connects those two houses). This means that, at least some of the time, our graph is disconnected. Thus, we can model our problem using a disconnected undirected weighted graph. For this problem, the input graphs are also simple graphs, meaning that any two nodes have only a single edge between them and that there are no edges connecting a node to itself. In the context of the MST problem, all self-edges can safely be ignored (as they would increase the total cost of a MST without expanding the connected area), and multiple edges between the same node can be eliminated by removing all but the minimum weight edge between two nodes (as the other edges have no chance of making it into a MST because the minimum weight edge between the two nodes will always be the better choice). A versatile MST calculating program should be able to account for non-simple graphs with no extra pre-processing, although this was ultimately unnecessary for this problem, since the input graphs are all simple graphs.

##### Minimum Spanning Trees

So what is a MST anyway? Let's formalize. Let $G = (V, E)$ be a connected graph with a collection of nodes (vertices) $V$ and a collection of edges $E$. Each vertex is identified by a label. Each edge is a 3-tuple containing the labels of the two nodes that the edge connects, and the weight (cost) associated with that edge. Let $G_{ST}$ be a spanning tree (ST) of $G$. $G_{ST}$ must have the following properties:

• $G_{ST} \subseteq E$, A ST of $G$ is a subset of the edges of $G$. This means that a ST is a collection of edges. A ST is technically a subgraph of $G$ (not a collection of edges), but for our problem we can relax this definition.
• $|G_{ST}| = |V| - 1$, There is exactly one fewer edge in a ST of $G$ than there are vertices in $G$. This is because a ST is a tree, and trees are acyclic. If there are $|V|$ or more edges, then this means there must be at least one cycle, violating the acyclic property of trees.

Let $G_{MST}$ be a minimum spanning tree of $G$. Let $ST_{G}$ be the collection of all spanning trees of $G$. $G_{MST}$ must have the following properties:

• $G_{MST} \in ST_{G}$ A MST of $G$ is also a ST of $G$.
• $\forall G_{ST} \subseteq ST_{G},$ $\sum_{x \in G_{ST} } x_{w}$ $\geq$ $\sum_{x \in G_{MST} } x_w$ where $x_w$ is the weight of edge $x$. The weights of the edges in a MST of $G$ must be less than or equal to the sum of weights in any spanning tree of $G$. This means that $G_{MST}$ minimizes the weights of a spanning tree of G, which is where the minimum spanning tree gets its name.

That was a lot of mathematical notation to describe what is a reasonably simple concept. In short, a minimum spanning tree of a connected graph is a collection of edges such that every node in the graph has a single path to every other node in the graph, and no other collection of edges with this property has a lower sum of weights. Note that I was careful to say a MST and not the MST. MSTs are not guaranteed to be unique, which is why this problem asks for the sum of weights of a MST rather than some set of edges comprising a MST. All MSTs for a given graph have the same sum of weights. This can be concluded directly from the second condition above.

But wait... this definition is only true for connected graphs, and the input for this problem includes disconnected graphs. This is important. There are several famous algorithms for calculating MSTs of a graph. The two with which I am most familiar are Prim's algorithm and Kruskal's algorithm. Out of the box, Prim's algorithm does not work on disconnected graphs. Kruskal's algorithm, however, can be used to calculate a minimum spanning forest without any modifications. The minimum spanning forest is a collection of minimum spanning trees for a disconnected graph: there is one tree in the forest for each connected component of the graph. Prim's algorithm can be modified to calculate a minimum spanning forest (one particpant's submitted solution did this), but I used Kruskal's algorithm to solve this problem.

##### Input Format

Before I describe Kruskal's algorithm, allow me to provide some explanation for the input format of this problem. Consider the following input for a test case:

3
0 2 1 5 2 6
1 1 2 4
2 0


The first line in this test case means that there are three houses in our power network. The houses are always labeled starting with 0 and going up to n-1 where n is the number of houses in the network. The next n lines describe the graph, in what closely resembles an adjacency list. Each line starts with the label of a house. The next number in the line, e, describes the number of previously unaccounted-for edges connected to that house (more on that later). The rest of the line consists of e pairs of values. The first value of each pair is the label of another house in the network. The second value of each pair is the monthly cost of the power line between the two houses described by the first value in the pair, and the value at the beginning of the line.

To work out the example test case above, we can see there are two previously unaccounted-for edges that connect to house 0. One of these edges connects to house 1 and has a weight of 5. The other connects to house 2 and has a weight of 6. Onto the next line...

House 1 has one previously unaccounted-for edge. This edge connects to house 2 and has a weight of 4. We know that house 1 also has an edge connecting it to house 0. This is where the previously unaccounted-for part comes into play. In a standard adjacency list for an undirected graph, every edge is present in the list twice: once for each node that it connects. As its input, Kruskal's algorithm takes a list of every edge. If the test cases for this problem were standard adjacency lists, the programmer would have to implement some extra pre-processing steps to remove the duplicates. This isn't necessarily very difficult, but it is more convienent to read in each edge exactly once.

Finally, house 2 has 0 unaccounted-for edges, since the edges to house 0 and house 1 have already been accounted for on previous lines. In every test case, the last house of the test case will always have 0 unaccounted-for edges.

Each input may have more than one test case (a test case looks like the example above). The first line of each input specifies the number of test cases. This is done to prevent participants from submitting simple programs like print(10) to try to get some free points on any test cases where the output might just be 10.

##### Disjoint-set Forests

Before we discuss Kruskal's algorithm, we must first discuss the data structure that lies at its core: the disjoint-set forest. The disjoint-set forest is a data structure that can be used to keep track of sets of items. Kruskal's algorithm treats connected componenets of graphs as sets, with the nodes in these components being the members of the set. If there exists some path (series of edges) between two nodes in the graph, then these two nodes are part of the same set. The disjoint-set forest has three essential operations: $MakeSet$, $Find$, and $Union$.

$MakeSet$ makes a new set which is kept track of internally as a tree. Each node of this tree is a member of the same set. Each node of the tree has a couple of properties: a pointer to its parent node, and a numerical value called the rank of the node (more on that later). Calling $MakeSet$ will initialize a set with a single node in its tree. This node should be initialized with rank 0 and with the parent property pointing to itself.

$Find$ returns a representation of a given set. This means that if we have two items of the same set $x, y$, then $Find(x) = Find(y)$. But what does representation of a set mean? A representation of a set is just a specific member of the set. It is important that each member of the set return the same representative element when we call $Find$ on it. Since we keep track of our set as a tree, our set representative is the root node of the tree. Thus calling $Find$ on a node in our set just traverses the tree up to the root node and returns the root. This ensures that each node in the set has the same representative, since a tree has only one root node.

$Union$ combines two sets together. Let's say we have two sets that we want to union: $A$ and $B$ ($A$ and $B$ are just members of sets, but we can call $Find(A)$ and $Find(B)$ to get the root nodes of those sets). If we call $Union$ on these sets, we want them both to be part of the same tree. There are two ways we can do this: make the root node of $A$'s tree have a parent pointer pointing to some node in $B$'s tree, or make the root node of $B$'s tree have a parent pointer poining to some node in $A$'s tree. For correctness sake, it doesn't actually matter which one you pick. No matter which you choose, the root node of the resulting tree will still be the same for every element of the set (thus for any elements $x,y \in A \cup B$, we have $Find(x) = Find(y)$). For now, let's say that $Union(A,B)$ will always make $B$'s tree's root node parent pointer point to the root element of $A$'s tree. I will give an example shortly to show why this is not ideal.

One of the most common uses of disjoint-set forests is to find connected components in a graph. Let's do that, considering the following unweighted undirected graph:

Just by looking at the image, we can see that this graph has two connected components: $\{A, B, C, D, E\}$ and $\{F, G, H\}$. Of course, for larger graphs with many intersecting edges, this task becomes impossible without the aid of computers. We start by calling $MakeSet$ on each node in our graph. Each node in the graph becomes the root node in a tree representing the set containing that node. Each tree node has the same label as the corresponding node in the above graph, and each node's parent pointer is initialized to point to the node itself. Our current disjoint-set forest looks like this:

Now we loop over every edge in our graph above. The order in which we loop doesn't matter if we are just looking for connected components. Let's start with the edge between $A$ and $B$. We know that $A$ and $B$ are in the same set, because there exists an edge between them. We call $Find(A)$ and $Find(B)$ and compare these values to discover that they are different ($Find(A)$ returns $A$ and $Find(B)$ returns $B$). Because we know they are connected (there exists an edge between them) but our $Find$ calls say otherwise, we call $Union(A,B)$ to merge the two sets. After our call to $Union$, our disjoint-set forest looks like this:

Great! Note that $Find(A)$ still returns $A$, but $Find(B)$ now also returns $A$, which indicates to us that $A$ and $B$ are in the same set. Now we will consider the edge between $C$ and $D$. Just like before, we check if $Find(C) = Find(D)$. It doesn't, but we know these nodes are in the same set, so we call $Union(C, D)$. Our disjoint-set forest now looks like this:

Now things start to get interesting... let's consider the edge between $B$ and $C$. $Find(B)$ returns $A$ and $Find(C)$ returns $C$, so we know we need to call $Union$. When we call $Union(B, C)$ we set $C$'s parent pointer to point to $B$. We get the following:

Now we are getting somewhere; $Find(A)$ $=$ $Find(B)$ $=$ $Find(C)$ $=$ $Find(D)$ $=$ $A$; we can easily verify that any of these nodes are part of the same connected component in our graph by calling $Find$ on them and comparing the values. With the way we built the tree, each call to $Find$ runs in $\mathcal{O}(n)$ time where $n$ is the number of nodes in each connected component. That's not great... fortunately there are some optimizations that let us get this down to nearly constant time. I say nearly because the amount of time taken does actually grow with respect to $n$. Specifically, the amortized cost of these operations are in $\mathcal{O}(\alpha(n))$, where $\alpha$ is the inverse Ackermann function. However, if we can guarantee that our input graph has fewer nodes in it than the number of atoms in the universe, then $\alpha(n)$ will always be less than 5. So for any practical input, the time complexity of these operations are in $\mathcal{O}(5) = \mathcal{O}(1)$, so we can guarantee constant time with this input size restriction. I will discuss these optimizations shortly. Fow now, let's finish our naïve disjoint-set forest.

Let's look at the edge between nodes $A$ and $D$. $Find(A)$ returns $A$ and $Find(D)$ returns $A$ as well. This means that nodes $A$ and $D$ are already in the same set, so we don't have to do anything. Onto the next edge! Let's consider the edge between nodes $A$ and $E$. These $Find$ calls returns different values, so we call $Union(A, E)$. Here is the resulting disjoint-set forest:

Looking good. When we process the edge between $D$ and $E$ we find that they are already in the same set ($Find(D)$ $=$ $Find(E)$), so we do nothing. For brevity's sake, I will perform the remaining construction with no explanation. The methodology used is exactly the same as it was in the preceeding paragraphs. Our final naïve disjoint-set forest looks like this:

This isn't ideal though. $Find(D)$ still takes 4 steps through the tree to return $A$ (linear time). We want our disjoint-set forest to look like this:

This way each call to $Find$ will take no more than 2 steps through the tree in the worst case (constant time). So how do we achieve a disjoint-set forest like this? We use the optimizations that I mentioned earlier. These optimizations are known as path compression and union by rank. Here is where the nodes' rank variable that I mentioned earlier comes into play. The path compression optimization is implemented in the $Find$ function, and the union by rank optimzation is implemented (unsurprisingly) in the $Union$ function. We will discuss path compression first.

###### Path Compression

The naïve way of implementing $Find$ might look something like this:

Find(node)
if node.parent == node
return node
else
return Find(node.parent)


If a node's node.parent property is pointing to itself, then we have reached the root of the tree and can return the node. Otherwise, we return the result of calling $Find$ on the parent in order to step up the tree one level repeatedly until we get to the root node. But what if we can mutate our tree while we traverse up through it? Each node's parent needs only to point to the root of the tree. We can change the parent pointers of each node along the path to the root to point directly to the root node. We are compressing the paths from the query node (and all nodes on the way up) to point directly to the root node. This improved implementation might look like this:

Find(node)
if node.parent == node
return node
else
node.parent = Find(node.parent)
return node.parent


On subsequent calls to $Find$ with the same query node, we now return in constant time. As an added bonus, calling $Find$ on any nodes along the path from the query node to the root also return in constant time. Awesome! Now let's consider union by rank.

###### Union by Rank

The naïve way of implementing $Union$ might look something like this:

Union(A,B)
Find(B).parent = A


We are making the root node of the set in which $B$ is a member point to $A$ as its parent, essentially splicing $B$'s set into $A$'s set. We can make a very easy optimization that will reduce the height of our trees dramatically:

Union(A,B)
Find(B).parent = Find(A)


This will cause $B$'s tree to get added just below the root of $A$'s tree, shortening the paths from the nodes of $B$ to $Find(A)$. This is a big improvement, but we can still do better. In general, we want our trees to be as short as possible, to reduce the number of steps that each $Find$ operation takes to get to the root. Let's say the tree with node $B$ has height 5 and the tree with node $A$ has height 3. If we set $B$'s tree's parent pointer to point to the root of $A$'s tree, then our resulting tree has height 6 (the height of $B$'s tree plus one more for the new tree root). However, if we set $A$'s tree's parent pointer to point to the root of $B$'s tree, then our resulting tree has height 5 (since the height of $A$'s tree was less than the height of $B$'s tree, so $B$'s tree still has the same height). We can achieve shorter trees by being smarter about which tree we append to the other.

So how can we be do this? We want to always append the shorter tree to the taller tree to avoid increasing the overall tree height. By keeping track of the maximum heights of each tree, we can accomplish this. The rank variable on each node is used to keep track of this maximum possible height. We call this variable rank instead of height because the actual height of a tree can be changed via path compression; height would be misleading, as this variable does not represent the actual height of the tree, only the maximum possible height.

Recall that the rank of each node is initialized to 0. We change our $Union$ operation to the following:

Union(A,B)
rootA = Find(A)
rootB = Find(B)
if rootA.rank < rootB.rank
rootA.parent = rootB
else if rootA.rank > rootB.rank
rootB.parent = rootA
else if rootA.rank == rootB.rank
rootB.parent = rootA
rootA.rank = rootA.rank + 1


There are three conditions here. If the rank of the set containing $A$ is less than the rank of the set containing $B$, then we change $A$'s tree's root parent pointer to point to $B$'s tree's root, as the tree containing $A$ is shorter than the tree containing $B$. If the rank of the set containing $B$ is less than the rank of the set containing $A$, we do the opposite: appending the tree containing $B$ to the root of the tree containing $A$. If the two ranks are equal, there is nothing clever we can do. We simply append one tree to the other and then increment the rank of the new root node (as the full tree's height now increased by one). Union by rank prevents us from growing our trees in a linear fashion like we did in the example above.

Together, path compression and union by rank improve the amortized time complexity for our $Find$ and $Union$ operations from $\mathcal{O}(n)$ to $\mathcal{O}(\alpha(n))$, which is just $\mathcal{O}(1)$ for any practical $n$. I will not present the analysis that leads to these results, but the third edition of CLRS covers it in depth in section 21.4 (it takes them eight and a half pages).

##### Kruskal's Algorithm

Now that we understand disjoint-set forests, let's discuss Kruskal's algorithm. Don't worry; we are almost there. The disjoint-set forest does all the heavy lifting for us. Let's say we have the nodes of our graph in a list called nodes and the edges of our graph in a list called edges. Each edge is a 3-tuple and has the following three datums: the label of a node $A$, the label of a node $B$, and a weight. The edge connects node $A$ to node $B$ with the specified weight. The entire pseudocode for Kruskal's algorithm is as follows:

mstEdges = {}
for each node in nodes
MakeSet(node)
sort edges by weight
for each edge in edges
setA = Find(edge.A)
setB = Find(edge.B)
if setA != setB:
Union(setA, setB)


That's it! At the end of this code block, mstEdges contains exactly the edges of a minimum spanning tree on our graph. Let's break this code down. We start out by declaring an empty set of edges; we will add the edges of our MST to this set as we come across them. Next up, we call $MakeSet$ on each node in our graph. This will initialize a new set tree for each node in our graph. Then we sort the edges by weight in nondecreasing order. The edge with the lowest weight is in the first index of edges, and the edge with the greatest weight is in the last index of edges. We then process each edge in our graph. We call $Find$ on the two nodes that the edge connects. If these two calls to $Find$ do not return the same set representative, then we have found an edge in our MST. This is the lowest weight edge that connects setA to setB. We $Union$ the two sets together, and add our edge to our mstEdges set.

For this problem, we don't actually need to keep track of the entire MST, just the sum of the weights. So the pseudocode for the solution to this problem might look like this:

sum = 0
for each node in nodes
MakeSet(node)
sort edges by weight
for each edge in edges
setA = Find(edge.A)
setB = Find(edge.B)
if setA != setB:
Union(setA, setB)
sum = sum + edge.weight


I really like Kruskal's algorithm because of its simplicity. All we really do is sort the edges in nondecreasing order and keep track of the connected components as we add each edge to our MST. Most of the complexity exists in the implementation of the disjoint-set forest, which is very good at finding spanning trees out of the box. For a graph with $n$ edges, the running time of Kruskal's algorithm is $\mathcal{O}(n \lg n)$, which is just the time it takes to sort the edges (this isn't quite true. If we have 0 edges and $m$ nodes in our graph, we still call $MakeSet$ $m$ times. Our real runtime is $\mathcal{O}(m + n \lg n)$, but for any interesting graph the $n \lg n$ portion dominates).

If you want to learn more about Kruskal's algorithm, I recommend reading section 23.2 of the third edition of CLRS. Chapter 21 of the third edition of CLRS also covers disjoint-set data structures in more detail than presented here.

##### Code Solution

The full Python code for my solution is below:

# With path compression and union by rank, performing N operations on the
# DisjointSet will result in a running time that is almost linear on N. While
# it is strictly superlinear, in the case of this problem the input constraints
# can be used to place a linear upper bound on the running time.
class DisjointSet:
# We make sure that the node's parent is set to itself to start, and that
# the rank of the node is 0.
def make_set(x):
x.p = x
x.rank = 0

# We link the two nodes that are representative of the set for x and y.
def union(x, y):

# We link the two nodes x and y.
# Here we are using union by rank to keep the asymptotic complexity
# as low as possible.
# If x's rank is greater than y's, y is set as a child of x.
if x.rank > y.rank:
y.p = x
else:
x.p = y
# If the ranks are equal, we must increase the rank of the new
# parent (y).
if x.rank == y.rank:
y.rank = y.rank + 1

# We find the representative node for x, which is the root node for the
# tree of which x is a member.
def find_set(x):
if x != x.p:
# Here we perform path compression by making sure that the root
# node is the parent of as many nodes in the tree as possible,
# which speeds up future accesses.
x.p = DisjointSet.find_set(x.p)
return x.p

# The Node object. This is a node in our DisjointSet, not a node in our input
# graph. It is initialized with the id of the vertex in our input graph.
class Node:
def __init__(self, id):
self.id = id

# T is the number of test cases.
T = int(input())

# Iterate over our test cases
for _ in range(T):
# num is the number of vertices in our graph.
num = int(input())

# We maintain a set of the vertices, to make sure we have the ids for
# each one.
vertices = set()

# We also maintain a set of the edges in our graph.
edges = set()

# Our input gives us num - 1 lines, with each line containing the leading
# edge id, followed by the number of edges, and then a list of trailing
# edge ids and the edge weights.
# For example 5 2 7 11 9 10 means:
# There are two edges connecting with vertex 5, an edge to vertex 7 (with
# weight 11) and an edge to vertex 9 (with weight 10).
for _ in range(num - 1):
line = input().split(' ')
numEdges = int(line[1])
# For each edge specified in our input line
for i in range(numEdges):
# We add 2 to all indices to account for the leading edge and
# number of edges in our input line.
trailing = line[2 + i * 2]
# Add the leading and trailing edges to the set to make sure we get
# every vertex.
# We add the edge to our edges set. An edge is represented by a
# 3-tuple, (leading edge id, trailing edge id, weight)
# Since each edge in specified in our line has two space separated
# pieces, we can index to the edge specified with i * 2. We again
# add 2 to index past the leading edge id and number of edges, then
# add 1 to index to the weight.

# We will store our disjoint set forest in a dictionary. The keys of the
# dictionary will be the vertex ids, and the values will be the nodes of
# our disjoint-set trees.
forests = {}
for vertex in vertices:
# Create a node with the vertex and assign it to the key vertex,
# which is the id of the vertex.
forests[vertex] = Node(vertex)
# We call make_set on the node to assign its parent as itself and
# set its rank to 0.
DisjointSet.make_set(forests[vertex])

# Now we convert our edges set into a list, and sort it by edge weight.
edges = list(edges)
edges.sort(key = lambda edge: edge[2])

# We iterate over every edge. total keeps track of the sum total of all
# the weights of the edges that we add to our MSP.
total = 0
while len(edges) > 0:
edge = edges.pop(0)
# We call find_set on the leading and trailing ids of the edge in
# question.
set_trailing = DisjointSet.find_set(forests[edge[1]])

# We have found an edge that connects two componenets of our graph.
# This edge should be added to the MSP weight total.
# We must now union the nodes for our leading and trailing ids for
# this edge. Path compression and union by rank are used in this
# implementation of disjoint set forests to ensure maximum
# efficiency.
DisjointSet.union(forests[edge[0]], forests[edge[1]])
total += edge[2]

# Print out our total. On to the next test case!
print(total)


To generate the input graphs, I wrote a small Rust program. I hope to expand this program later to have more functionality. I'm sure I will write another Code-a-Thon problem that uses graphs at some point, so this will come in handy.

#### Problem 4: Tingle Towers

It is a USC Code-a-Thon tradition to include Tingle as backstory for at least one problem, thus the story for this problem was born. Slightly more students solved this problem successfully than the previous one (six versus five), but I suspect this was because the question was easier to Google. The only valid solution for division 2 included this comment:

# Borrowed kindly from https://www.geeksforgeeks.org/lcs-longest-common-subsequence-three-strings/


Oh well! We encourage Googling during the competition for two main reasons: we have no way to enforce a no-Googling policy (as students can participate from home or elsewhere), and the ultimate goal of our Code-a-Thons is to expose participants to more problems or types of problems in computer science, as well as getting them to practice implementing them in a competitive setting. As a participant in the USC Code-a-Thon several years ago, I learned about the matrix exponentiation method for rapidly calculating Fibonacci numbers. I implemented this by following pseudocode I found online, and I have not forgotten how it works to this day. My only hope is that the student whose code included the above comment took the time to read the article and understand how the code worked instead of blindly copying and pasting. For the Code-a-Thon in which USC annually participants (ACM's ICPC), there is no internet access. We want students to Google solutions now so that they will remember them later.

##### Longest Common subsequences

Anyway, on to the problem. If you read the above code comment you have probably figured out that this problem boils down to finding the longest common subsequence of three strings. Each test case presents three strings made up of the characters R, G, and B. The goal is to find the length of the longest sequence of Rs, Gs, and Bs such that this sequence is a subsequence of every input string. Before diving into the solution, let's formalize our understanding of a subsequence.

First of all, a sequence is some collection of elements where the order of the elements in the collection is important. A subsequence is a sequence built from some other subsequence by removing zero or more elements from the original sequence (but preserving the relative order between all other elements). For example, the sequence $\langle 1, 2, 3 \rangle$ has many subsequences: $\langle 1, 2, 3 \rangle$ (obtained by removing no elements from the original sequence), $\langle 1, 2 \rangle$, $\langle 2, 3 \rangle$, $\langle 1, 3 \rangle$, $\langle 1 \rangle$, $\langle 2 \rangle$, $\langle 3 \rangle$, and $\langle \rangle$ (the empty sequence, obtained by removing all of the elements from the original subsequence).

A common subsequence of two sequences $A$ and $B$ is some sequence that is both a subsequence of $A$ and a subsequence of $B$. A longest common subsequence $LCS$ of two sequences $A$ and $B$ is some common subsequence of $A$ and $B$ such that there exists no other common subsequence of $A$ and $B$ that has more elements than $LCS$. These can be generalized from two subsequences to arbitrarily many subsequences.

For example, given the sequences $A = \langle 1, 2, 3, 1, 2, 3 \rangle$, $B = \langle 1, 1, 1, 1, 2, 2, 1, 1 \rangle$, $C = \langle 1, 1, 2, 2, 2, 3 \rangle$, a $LCS$ of $A$, $B$, and $C$ is $\langle 1, 1, 2 \rangle$. Note that this is not the only $LCS$ of $A$, $B$, and $C$. For example, $\langle 1, 2, 2 \rangle$ also fits the critera. Both of these have length three, and there is no length four subsequence that is common to $A$, $B$, and $C$.

##### Naïve solution

The naïve algorithm to solve this problem finds every possible subsequence of the shortest input string, and checks each one for its existence in the other two input strings. If the subsequences are calcuated in decreasing order of length (starting with the entire sequence, then all subsequences with length one shorter than the sequence, etc.), then as soon as we find a match we return right away. If we exhaust all possible subsequences, then we return the empty sequence. This algorithm is a fairly intuitive brute force solution. The time it takes for this solution to solve the problem grows with the number of subsequences of the shortest input string. For each subsequence, we do a linear amount of work to check if the subsequence is a subsequence of the other input strings. So how many subsequences does a sequence of length $n$ have?

We note that the sequence of length $0$ has exactly one subsequence: the empty sequence. Let us consider a sequence $S$ of length $k$. $S$ has some unknown number of subsequences $n$. Now consider some element $x$. We append the element $x$ to the sequence $S$ to make a new sequence $S'$ of length $k+1$. We note that all $n$ subsequences of $S$ are still subsequences of $S'$, because a subsequence is made by removing some arbitrary number of elements from the sequence, so the element $x$ can be removed in each of these cases. We also note that the new subsequences of $S'$ (those that were not subsequences of $S$) are exactly the subsequences of $S$ with $x$ appended to the end. In other words, for any subsequence $Q$ of $S'$, $Q$ is either exactly a subsequence of $S$ or some subsequence of $S'$ with the element $x$ at the end, which is exactly some subsequence of $S$ with $x$ appended to it. This means that by adding $x$ to our sequence $S$, we have doubled the number of subsequences in $S'$. In general, a sequence of length $k+1$ has exactly two times the number of subsequences as a sequence of length $k$. Since the sequence of length $0$ has one subsequence, this means that a sequence of length $n$ has $2^{n}$ subsequences.

Thanks to mathematical induction, we know that our naïve solution is in $\mathcal{O} (m \cdot 2^{n})$ where $n$ is the length of the shortest input sequence and $m$ is the length of the longest input sequence. For $n = m = 100$ (the upper bound for this problem) this algorithm would take just over 4000 years to produce an answer if we used all of the computing power in the world (using this 2015 estimate). This calculation makes the incorrect assumption that each operation of our algorithm is a floating point operation, but our time estimate is accurate enough for us to realize that clearly this is not the correct approach.

Let's break down the problem and figure out a better way to solve it.

##### Analysis of LCS Problem

For ease of analysis, we will assume the LCS problem with only two input strings (rather than the three provided by this problem). We will generalize later to $n$-dimensions, and then use $n=3$ to write a solution. Because this problem asks for the length of a longest common subsequnce, we just need to find any LCS of our inputs to figure out our answer (the length of the LCS).

Let's try working through our sequences backwards. Consider two sequences $A$ and $B$, of lengths $n$ and $m$. I will use the notation $S_{x..y}$ to indicate a contiguious subsequence of $S$ from index $x$ to index $y$. For example: $A_{1..n}$ is the entire sequence $A$, and $A_{2..n-1}$ is the subsequence of $A$ with the first and last elements removed. If the last element of $A$ is the same as the last element of $B$ then we know this element will always be in a LCS of $A$ and $B$. We can safely remove the last elements from $A$ and $B$ and consider these truncated sequences with their last elements removed. If we find a LCS of these two truncated sequences, then we can simply append the element that we had previouly removed to the end of that LCS to get a LCS of $A$ and $B$. So when the last two elements of $A$ and $B$ are the same, $LCS(A_{1..n}, B_{1..m})$ $=$ $LCS(A_{1..n-1}, B_{1..m-1})$ $+$ $A_{n}$. This seems useful, but it only works when the last elements of our sequences are the same. What do we do if the last element of $A$ and the last element of $B$ are different? Since the last elements of $A$ and $B$ are different we know that they cannot both be in the same LCS (because if one is the last element of a LCS, the other cannot be the last element of the same LCS as it is different). Thus we have three cases:

• $A_n$ is in a LCS of $A$ and $B_{1..m-1}$ $\implies$ $LCS(A, B)$ $=$ $LCS(A, B_{1..m-1})$
• $B_m$ is in a LCS of $A_{1..n-1}$ and $B$ $\implies$ $LCS(A, B)$ $=$ $LCS(A_{1..n-1}, B)$
• $A_n$ and $B_m$ are not in any LCS of $A$ and $B$ $\implies$ $LCS(A, B)$ $=$ $LCS(A_{1..n-1}, B_{1..m-1})$

Now we are getting somewhere. In general, any time that we are recursively reducing the size of our input we are making progress towards a solution. If we can combine these three rules with the above rule (when $A_n$ is the same as $A_m$) then we can eventually reduce our problem to $LCS(A', B')$ where either $A'$ or $B'$ is the empty sequence. $LCS(A', B')$ is just the empty sequence, so when we reach this point we can start unwinding our recursion and use the $+ A_{n}$s above to figure out a LCS. Sweet.

We know that one of the above three cases must be true when $A_n$ and $B_m$ are different, since if all cases are false it would imply that $A_n$ and $B_m$ are both in some LCS, which we have already proven cannot happen. But how do we know which of these statements is true, and thus which path of recursion to travel down? In short: we can't. There is no way to know which of these is true without figuring out each one. This seems like a problem... when the last elements of our truncated sequences do not match we are making three recursive calls but only reducing our input size to each one by a single element. We can model this behavior as a recurrence relation:

\begin{aligned} T(n) &= 3 \cdot T(n - 1) + 1 \\ T(n) &= 3 \cdot (3 \cdot T(n - 2) + 1) + 1 \\ T(n) &= 9 \cdot T(n - 2) + 2 \\ T(n) &= 9 \cdot (3 \cdot T(n - 3) + 1) + 2 \\ T(n) &= 27 \cdot T(n - 3) + 3 \\ \dots \\ T(n) &= 3^{n} + T(n - n) + n \\ T(n) &= 3^{n} + 1 + n \\ \Downarrow \\ T(n) &\in \mathcal{O} (3^n) \\ \end{aligned}

Oh no! Our recursive solution doesn't appear to be any better than the naïve one! Fear not: we are closer than it appears.

First of all, we have shown that the solution to an instance of the LCS problem can be obtained from the combination of the solutions to that instance's sub-problems. This is known as optimal substructure, and is an important property to look for when attempting to solve a problem. During our recursion, we are performing a lot of duplicate work. Consider the following example: we are calculating $LCS(A, B)$ where $A$ has length $10$ and $B$ has length $10$. Let's look at the sub-problem $LCS(A_{1..5}, B_{1..5})$. This sub-problem is called in the $LCS(A_{1..6}, B_{1..5})$ subproblem, but also in the $LCS(A_{1..5}, B_{1..6})$ and $LCS(A_{1..6}, B_{1..6})$ sub-problems.This is known as overlapping sub-problems. Whenever we have both optimal substructure and overlapping sub-problems, we can apply dynamic programming to speed up our algorithm.

##### Dynamic Programming Solution

The key concept of dynamic programming is recording the results of the overlapping sub-problems so that the next time they are called, we can look up our already-computed answer instead of recalculating it. This concept is known as memoization, and is a powerful tool in preventing algorithms from doing duplicate work. Often we implement memoization as a table; each entry of the table corresponds to a specific sub-problem of the inital problem. For the LCS problem, the sub-problems are each possible combination of truncated sequences of $A$ and $B$. If $A$ has length $n$, there are $n$ possible truncated sequences of $A$. If $B$ has length $m$, there are $m$ possible truncated sequences of $B$. This means that altogether we have $n \times m$ total sub-problems. It makes sense to use a two-dimensional table for the LCS problem applied to two inputs. As we move $/rightarrow$ in our table, we increase the number of elements in sequence $A$. As we move $/downarrow$ in our table, we increase the number of elements in sequence $B$. Tables are easier to visualize on computers than they are in our heads. Fortunately for both of us, you happen to be looking at one.

$1$ $2$ $\cdots$ $n$
$1$ $LCS(A_{1..1}, B_{1..1})$ $LCS(A_{1..2}, B_{1..1})$ $\cdots$ $LCS(A_{1..n}, B_{1..1})$
$2$ $LCS(A_{1..1}, B_{1..2})$ $LCS(A_{1..2}, B_{1..2})$ $\cdots$ $LCS(A_{1..n}, B_{1..2})$
$\vdots$ $\vdots$ $\vdots$ $\ddots$ $\vdots$
$m$ $LCS(A_{1..1}, B_{1..m})$ $LCS(A_{1..2}, B_{1..m})$ $\cdots$ $LCS(A_{1..n}, B_{1..m})$

We have used $LCS(A, B)$ a lot, but haven't really gone over what this function actually returns. This depends on what you want to know. If you are looking for the length of the LCS of $A$ and $B$, then $LCS(A, B)$ just returns the length of the LCS. If you are looking for an actual subsequence, LCS has to return something other that just the length. Despite not needing to find an actual subsequence for this problem, I will provide the algorithm for finding it, since it doesn't take much additional work.

"Wait a second..." you may be thinking. "This table only accounts for two inputs! The problem we are solving has three!" Yes, yes, I know. I haven't forgotten about the $n$-dimensional generalization. Unfortunately, HTML cannot easily render $n$-dimensional tables. The intuition for 2-dimensional vs. 3-dimensional vs. $n$-dimensional is very similar, so I will explain the algorithm for two dimensions (with visualizations) and then I will explain the formulation for the $n$-dimensional version. Finally, I will provide code for the 3-dimensional version. Don't fret! Back to the algorithm:

There are two main approaches for solving dynamic programming problems. The top-down approach attempts to delay filling out entries in the table until they are needed. The bottom-up approach fills out the entire table first before attempting to solve the actual problem. In my experience, bottom-up is usually the easier, or more intuitive approach. The top-down approach sometimes involves many constant-time duplicate table lookups which can impart a performance penalty. With bottom-up we have more control over the order in which we fill out the table. That said, both approaches are equivalent in terms of their validity. I will present the bottom-up approach for this problem: we will start filling out our table in the top left (when $n = m = 1$) and work our way to the bottom left (when $n$ and $m$ are at their maximal values). When we finish filling out the table, our answer will be sitting in the bottom left entry of our table, ready to be plucked out and returned.

What do we need in an actual table entry? There are two important pieces of information we need to store: the length of the LCS at that point and a direction that points toward the previous element in the LCS. The direction aspect will make more sense shortly. Let's work out an example, filling out a table as we go.

Our input sequences will be KERNIGHAN and RITCHIE. Let's make a blank table. In this example, we are going to zero-index our sequences and table to make it easier to convert to code later. Here is our empty table:

R I T C H I E
K
E
R
N
I
G
H
A
N

We have all possible combinations of subsequences of our two inputs here. Note that this includes the empty sequence. We know that the length of the longest LCS between the emtpy sequence and any sequence is 0, so we fill in these entries with a 0.

R I T C H I E
$0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$
K $0$
E $0$
R $0$
N $0$
I $0$
G $0$
H $0$
A $0$
N $0$

Now we are going to start filling out our table, starting in the top left. Recall the general recursive procedure that we identified earlier:

1. If $A_n = B_m$ then we remove the last elements of $A$ and $B$ and increase our LCS length by one. We are finished and can return.
2. If $A_n$ and $B_m$ are different, we make three recursive calls: i) A recursive call with the last element of $B$ removed ant $A$ left intact ii) A recursive call with the last element of $A$ removed and $B$ left intact iii) A recursive call with the last elements of $A$ and $B$ removed
3. Take the maximum of the three recursive calls and return.

In the top left corner, we have $A_n =$ R and $B_m =$ K. R and K are different of course, so we must make three recursive calls. Our table already has the values saved for these three calls! They are the three bordering table cells to the top left. If we want to think of these in terms of coordinates, for an entry T[x][y], the values for our three recursive calls are in T[x-1][y], T[x][y-1], and T[x-1][y-1]. The maximum of three zeroes is, of course, zero, so we put zero in our table and pick a default direction, let's use $\uparrow$. The direction is used to indicate which element we removed from our sequence. $\uparrow$ indicates that we removed an element from our $B$ sequence (in this case KERNIGHAN). $\leftarrow$ indicates that we removed an element from our $A$ string (RITCHIE). $\nwarrow$ indicates that we removed an element from both sequences. This will become more clear shortly.

R I T C H I E
$0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$
K $0$ $\uparrow 0$
E $0$
R $0$
N $0$
I $0$
G $0$
H $0$
A $0$
N $0$

Let's move down the first column. E and R don't match so we do the same thing as before. The max of all our recursive calls is zero, so we fill in a zero and our default direction ($\uparrow$). The next table cell is more interesting. R and R match! Referring back to our procedure, we want to remove an element from both sequences and increase the LCS length by 1. We point $\nwarrow$ (because we removed an element from both sequences) and set our LCS length to be $LCS(A_{1..2}, B_{1..1}) + 1$ (the value in the cell one cell $\nwarrow$ from the current cell). Here is what our table looks like:

R I T C H I E
$0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$
K $0$ $\uparrow 0$
E $0$ $\uparrow 0$
R $0$ $\nwarrow 1$
N $0$
I $0$
G $0$
H $0$
A $0$
N $0$

##### Code Solution

The full Python code for my solution is below:

# Read in number of test cases.
t = int(input())

# For each test case.
for _ in range(t):
# Read the number of zucchinis.
n = int(input())

# Grab the heights of each zucchini in a list.
heights = list(map(int, input().split(" ")))

# Build our other list and initialize to False. We use two extra indices
# to avoid having to do bounds checking.
expect_next = [False] * (n + 2)

# We keep track of the number of sequences we have found in count.
count = 0

# For each zucchini, if we have not seen the previous zucchini
# (with height - 1) we increase our count by 1. We then set the value for
# our next zucchini (with height + 1) to True, indicating we expect to see
# it further along in the sequence.
for h in heights:
if not expect_next[h]:
count += 1
expect_next[h + 1] = True

# We take the ceiling of the log_2 of count...
log = 0
while 1 << log < count:
log += 1

# And print out our answer.
print(log)


## Conclusion

Wow, when I started writing this solution guide I did not expect to reach 10,000 words, let alone 20,000. I know that was a lot to read, but I hope if you stuck through it that you learned something that you may be able to apply in your schoolwork, a Code-a-Thon, a technical interview, or some other programming endeavor. These types of problems may not come up every day, but when one does, having an efficient solution can be all the difference in the world.

To those who participated in the Code-a-Thon, thank you for your participation. I love writing Code-a-Thon problems, but it would all be for naught if there were not bright students eager to solve them. Thanks again to the University of South Carolina and the Department of Engineering and Computing for providing space and support for the Code-a-Thon. Thanks to USC-ACM for support in organization and advertising (and for being the computing club of choice for most of our participants)! Thanks to Krumware for providing pizza in a solid attempt to placate the insatiable hunger of a room full of collegiate programmers. Lastly, I thank my wonderful Mom who proofread this entire post despite never before having read a single line of code.

If you have any questions or you have found any errors, please e-mail me at jadaytime (at) gmail.com. Unfortunately I can't send you a hexadecimal dollar, but I will be very grateful nonetheless.