2015 Round 1A

If a count is strictly larger than the following count, then Kaylin must have eaten the difference, and possibly more if Bartholomew added mushrooms.

Thus with the first method we minimize the number of eaten mushrooms if in such cases we assume Kaylin ate exactly the difference, and Bartholomew added no mushrooms. For the other counts, we can assume Kaylin ate nothing.

In other words, if ms is the list of mushroom counts, then the clipped successive differences are:

and these are lower bounds for the number of mushrooms eaten between intervals. For the first method, there are no other constraints so the answer is simply the sum.

For the second method, since Kaylin eats at a constant rate when possible, we acheive the minimum by taking this constant to be the maximum of the above list. Then we simulate eating at this constant rate to compute the total mushrooms eaten. In each interval except the last, Kaylin eats the lesser of the number of mushrooms on the plate and our chosen constant.

I realized later my original solution was wrong, but I got away with it because both inputs never exercised the bug. In the first version of my code, I only applied max 0 to ds for the first method, and skipped it for the second method, so that the chosen constant was simply the maximum of the unadulterated successive differences. Why is this bad?

It all goes wrong if we are given a strictly increasing sequence, for then all the sucessive differences are negative, and we choose a negative constant eating rate for the second method, which is nonsensical. During the simulation, Kayling eating negative amounts of mushrooms results in a nonsensical negative total.

I suppose the test inputs were randomly generated and of moderate length, thus the probability of producing a strictly increasing sequence was negligible.

The limit for N is so large that brute force simulation is out of the question for the small input.

However, a simple trick makes simulation feasible for the small input. Let ms be the haircut times, and let X be their least common multiple. Then every X minutes, the same number of customers Y are served and all barbers are ready. This number Y is simply the sum of the quotients resulting from dividing X by each element of ms.

Thus we can solve the problem for (N mod Y) customers instead. The small dataset limits imply that Y is always small enough that simulating this with brute force is feasible.

There are at most 5 barbers, so we may as well use Data.List to find the barber who will be ready next and to subtract minutes from all barbers to advance to the next state.

The barbers are one-indexed while Haskell lists are zero-indexed, explaining the additions and subtractions by 1.

How about the large dataset? The above trick no longer works. Fortunately, by tweaking one of our ideas slightly, we soon crack this problem. Before, after determining the least common multiple X, we still had to figure out Y, the number of customers served after X minutes. This was easy: we sum a bunch of quotients.

This leads us to consider picking any number Z and computing the number of customers served in the first few Z minutes. Since Z is no longer guaranteed to be a multiple of each element of ms, some of the barbers might still be busy. This is fine, so long as we’re clear that our count includes the customers still being served. That is, "customers served" includes those still in the middle of a haircut. We compute this for each barber by rounding up to the nearest integer Z divided by the time taken.

Suppose after 2468 minutes, we’ve served (N - 4) customers, and after 2469 minutes, we’ve served (N + 7) customers. Surely from this information it should be easy to figure out which barber is serving the Nth customer?

Indeed, we can consider each barber in turn and see if their customer count incremented between minute 2468 and 2469. The 4th of the barbers who received a new customer at minute 2469 is the answer.

So far so good, but how would we find minute 2468 in the first place? That is, how do we determine the exact minute where the count of customers served is less than N, but increases to N or above in the very next minute?

Since the number of customers served can only increase over time, we are led to consider binary search. An upper bound for such a search is N times the time taken by the fastest barber.

There are at most 14 trees at a time in the small dataset, so we can use brute force. For each tree, we try removing every possible subset of the other trees and compute the resulting convex hull.

This does require us to implement a convex hull algorithm, but we should practice this as it may help solve other problems.

A smarter and simpler method follows from a basic observation. Suppose there are at least two trees. The convex hull of the trees thus consists of more than a single point, and in particular, part of its boundary is a line between two trees. Then every tree in this lies on one side of this line, or on the line itself.

So for a given tree A, if we pick any other tree B and remove all trees on one side of the line AB or the other, then A will lie on the boundary. We can therefore try all possible choices for B, and find the minimum number of trees that lie on one side or the other.

We use the signed area to decide which side of a line a given point lies.

We need one more boost to solve the large input. It seems wasteful that for each choice of B, we must go through all the trees one by one and determine which side of AB they lie.

To address this, for a given tree A, we sort the other trees by their bearing from A with atan2, and place them in an array.

For each other tree B, we wish to find what we shall call its opposite tree, which we define to be the tree C whose bearing differs from the bearing of B by as close to but exceeding pi radians, with the smallest array index breaking ties. We can find C by looking for the first tree in the array such that the signed area of BAC is positive.

If no such tree C exists, then A and B lie on the boundary. Otherwise, if we remove all trees with bearing greater all equal to C along with those trees with bearing strictly less than B, then A and B will lie on the boundary of the remaining trees. The number of trees removed is the index of C subtracted from the index of B, modulo n - 1.

The answer is then the minimum number of trees removed over all trees B different to A. If we discover that A lies on the boundary at any point, we can short-circuit and return zero for the tree A.

We could determine B’s opposite tree with binary search for all B, but we can do better. If we iterate through the trees in anticlockwise order, then the corresponding opposite trees also show up in anticlockwise order. So for each tree B, we find its opposite tree with a simple linear search starting from the previous tree’s opposite tree, amd this implies overall we will have iterated through all trees two times at most when searching for opposites, reducing a logarithmic factor to a constant.

We could avoid floating-point arithmetic by replacing atan2 with a sign comparison followed by a ratio comparison, because we never need the actual angle; we only need the trees to be sorted by bearing.