2014 Round Two

I first solved this with C, using a sort of greedy algorithm. I started from the biggest remaining file, and searched for the largest remaining file that could be paired with it; if none existed then we write the big file to a disc by itself. I stored the number of files of each size in an array, which I used to handle several cases at a time.

Later I realized we can do something simpler: pair the biggest remaining file with the smallest remaining file if their combined size fits on a single disc, otherwise we put the large file on a disc by itself. [Exercise: why does this also work?]

This algorithm works nicely with a doubly linked list. We start a pointer at either end then step them towards each other until they cross paths.

We approximate this in Haskell with two lists: the original list, and its reverse. A troublesome case arises when all remaining files have the same size. In a real doubly linked list, we can just wait until one pointer reaches the other, but our code instead manipulates the lengths of the lists to calculate r, the number of remaining files.

Then if two of them can fit on a single disc, we need r/2 discs when r is even, and (r+1)/2 when r is odd. We calculate this with the unorthodox uncurry (+) $ divMod r 2 to flex our functional programming muscles. Otherwise, if we can only fit one file per disc, we clearly need r discs.

We can brute force the small case: we print the minimum number of inversions over all permutations that result in an up-and-down sequence.

Brute force is often the best first move: we can code it quickly to solve the small case, and score some points. It takes longer to design and code a clever algorithm, and even if we think of one immediately, it is good to have a simple brute force program to compare against to catch bugs.

Admittedly, this program cuts it close on slower machines. If we happen to be competing with an older computer, we may be better off with C.

How about the large case? Our first instinct may be to figure out what to do with the maximum and work our way down the other numbers. However, there are some cases where it’s unclear where we should move the maximum number.

The trick is to consider the opposite: start from the smallest number and work our way up. The smallest number must wind up on the extreme left or right. We choose the closer extreme. Then we can ignore this number and recurse on the remainder of the list.

But this means when working on a given number i, we ignore all numbers less than i, so we can compute the answer without actually moving anything. For each number i, count the number of element larger than i on its right and on its left, then add the minimum of the two to a running sum. We use an array instead of a list for constant time lookups.

A reminder to read problems carefully: the first time around, my eye skipped over "adjacent" when reading the problem, despite the word being bold and italicized. The examples work either way. As a result, I wasted time coding a solution to the wrong problem.

This is a maximum flow problem, but thankfully one with enough constraints that we can use a simple algorithm: we start at the south of the river, at the leftmost unblocked square. Then we try to reach the north side using the left-hand rule for solving mazes (allowing our path to intersect itself).

If we make it, we increment a counter, and mark all the squares we traveled as blocked, otherwise we leave everything alone. We repeat this for every unblocked square on the south side, going left to right. The final value of the counter is our answer.

Why does this work? Here’s a rough explanation.

Suppose we’re wrong, that is, there is some way of obtaining more flow in the river. Then consider the path P that starts from the leftmost square X that is not the start of a path in our solution. Somehow our algorithm failed to find it, which could only happen if P conflicts with a path Q starting from some square Y to the left of X. (The left-hand rule always finds a path across the river if one exists.)

By definition, the correct solution has some path Q' also starting from Y. Since we use the left-hand rule, inductively, each step of Q' must be a step of Q, or strictly to the right of a step of Q. This implies each step of P must be strictly to the right of each step of Q, which means our algorithm would have found some path starting from X. This is a contradiction.

It’s easier to code a left-hand maze solver if we proceed one tile at a time. The small input case is small enough that we can store the map of the river in a two-dimensional array:

The much longer river in the large input means stepping one tile at a time is infeasible. Instead, we must compute entire line segments at a time. Given a direction and a building our left hand is touching, we try every building in turn and see if it intersects before we reach the corner of the touched building.

We need a couple of optimizations. Firstly, instead of marking every path on the map as a new obstacle, we only remember the last path found: since we’re working left to right using the left-hand rule, the only old path we can touch is the previously found path. Secondly, we coalesce consecutive path segments going in the same direction into one long path (cull).

We would benefit from sorting the coordinates in a tree, and removing buildings touched by previous paths, but it turns out our code is adequate.

The first time around, I made a mistake that would have been catastrophic in a contest: I thought I could make one pass over the path and remove adjacent entries with identical coordinates, then make a second pass to remove adjacent entries facing identical directions. However, this fails in some cases, and is anyway more complicated then our above cull function.

I also cheated in the sense that I had to try an initial version of my program on the large input before realizing more optimizations were needed. I should be generating my own large test cases to do this.

The small input is amenable to brute force. Our first sub-problem is to generate all partitions of a set into N pieces. The number of such partitions is given by Stirling numbers of the second kind, and we enumerate all partitions using the same ideas underpinning a well-known recurrence for these numbers.

Namely, to partition M elements into N sets, we can either put the Mth element in a singleton set and partition the remaining M - 1 elements in to N - 1 sets, or partition the remaining M - 1 elements in to N sets and add the Mth element to one of them.

For each partition, we reuse the ins function from our second solution to File-Fix-It to insert each of the N subsets into a tree, and count the number of created nodes. We then find the maximum of these numbers, along with the number of times the maximum occurred.

For convenience, we place a newline character in the root node, which is safe because it never appears in an input string.

We’ll need a much cleverer approach for the large input.

The worst-case number of nodes is relatively easy. If X strings share a certain prefix, then in the worst case, those strings must be sprayed across as many servers as possible: if X is less than N, they must be assigned to X different servers; otherwise, they are assigned them to N different servers. [Suppose not, that is, suppose in some worst-case scenario, there exists a server with at least two strings with the prefix, as well as a server which completely lacks such strings. Then what happens when we move one of those strings from one server to the other?]

Thus we insert all the strings into a single trie, and compute the worst-case number of nodes with a straightforward recursion (worst). There’s one subtlety: we must distinguish between, for example, a tree containing just "aaa", and a tree containing both "aa" and "aaa".

We do so by artificially appending a newline character to end of each input string. Since this character never appears within a string, it gives us a one-to-one correspondence between the input strings and the leaf nodes of the trie.

The product of the upper bounds (100, 100, 1000) gives us a crude upper bound for the worst-case number of nodes, so we know we can avoid modular arithmetic for now.

Finding the number of worst-case scenarios is the hardest part of this problem.

Consider an internal node P. Suppose one of its children Q is the root of a subtree with at least N leaf nodes. From above, we know that the leaves of this subtree must be sprayed across all N servers somehow or other, which implies that the node P must be created on all N servers.

Then suppose another child of P, say R, has r leaf nodes where r < N. We must assign the r leaf nodes to distinct servers so that R is duplicated as much as possible, but there are no other conditions because P is already everywhere. Thus if tally(x) is the number of worst-case assignments for the trie rooted at the node x, and exts(x) is the number of leaf nodes descended from the node x, then:

where fall is the falling factorial.

What if every child of P has fewer than N descendent leaf nodes? Since we know M is at least as large as N, and since we only need to call tally() on nodes with at least N descendent leaf nodes, we may assume P has at least N descendent leaf nodes spread among its children.

Our final sub-problem, then, is to count the number of ways we can distribute these leaf nodes among the N servers so that firstly, each server contains at least one such leaf node, and secondly, for every child Q of P, every descendent leaf node of Q lies on a distinct server.

Let xs = [x0, …​, xk] be the numbers of descendent leaf nodes of the children of P, and let m be their maximum (m = maximum xs). Let M be one of possibly several children of P with m leaf nodes. Let f(i) be the number of ways to distribute these leaf nodes to satisfy the two conditions on i servers, that is, each of the i servers has at least one leaf node, and the leaf nodes belonging to the same child of P are on distinct servers.

Trivially, f(i) = 0 for i < m, because there’s too few servers to distribute the leaf nodes of M so they end up in different places.

We can compute f(m) easily: for each child Q of P, we just count the number of ways its descendent leaf nodes can wind up on different servers:

This is because distributing the leaf nodes of M to distinct servers automatically ensures each server has at least one leaf node.

More generally, we can compute f(m + k) recursively. As before, we start by counting the number of ways the descendent leaf nodes of each child of P can wind up on different servers:

Then we subtract the cases where some servers miss out on at least one leaf node. Suppose we know f(i) for i < m + k. Then for each such i, we subtract the number of ways of picking i servers from the m + k multiplied by f(i), that is, the number of ways we can distribute the leaf nodes among these i servers so that the above conditions are satisfied:

where ch is the n-choose-k function.

There’s a few other details. We precompute n choose k and the kth falling factorial power of n for n and k between 0 and 100, and store them in arrays. Our arithmetic operations are performed modulo the number specified in the problem.

I made several mistakes that would probably have killed my chances in a real contest. I missed the subtlety with, for example, inputs containing "aa" and "aaa", but luckily this problem was exposed when comparing my second solution against the brute force solution.

More serious was my first attempt at computing tally. I had an inefficient recursion that in some sense was recomputing the same quantities over and over.