Jam 2015 Round 1A

Posted on 24th April 2015

So, I didn't do this one live, as it ran at 2am UK time... I did however, for fun, try this under timed conditions a few days later, and I didn't do great, but got enough to qualify (did A and B with 3 silly mistakes from B, then C small, and stupidly didn't think, and tried my slow algorithm on C large. As large problems are one-shot, it would have been game over, and I'd be around 500 in the ranking.)

As ever, links to: Official Contest Analysis and my code on GitHub.

Problem A, Mushroom Monster: Easy, and my solution doesn't differ from the official analysis.

Problem B, Haircut: Have B barbers where barber k always takes \( M_k\) time to perform a haircut. Customers are served by whichever barber is free first, and if there is a choice, the lowest numbered barber goes first. You are N in the queue. Who served you?

  • Let us say that if a customer has started having their hair cut (or it's finished) then they are "served".
  • So in time interval \( [0, T) \) barber k has served \[ \Big\lceil \frac{T}{M_k} \Big\rceil = \Big\lfloor \frac{T+M_k-1}{M_k} \Big\rfloor \] customers.
  • My method was to use a binary search for a good lower bound for T such that all k barbers have served fewer than N customers, and then a direct simulation to find exactly which barber serves N.
  • Actually, after the event, it's clear that the binary search can find T exactly, so you know N is served in at time T. Then work out how many customers have been served, which barbers are free, and you know the answer without simulation.

Problem C, Logging: Have integer lattice points which are trees. Want to know, for each tree, how many other trees do we need to remove so that this tree is then on the boundary of the convex hull of the remaining trees.

  • No idea how to begin, so Google (ahem) "convex hull algorithm" and find Gift Wrapping Algorithm the picture gives a great idea...
  • Suppose, for ease, no three trees are colinear. Then to be on boundary means to be vertex of the convex hull. Imagine walking around the convex hull: what the vertex before our tree? Call this S, and our tree T.
  • Then the vertex after these will lie on the right of the line from S to T. And consequently, any trees on the left of this (infinite) line must be removed. But no other trees need to be removed. (If you don't see this, draw some pictures).
  • If we allow colinear trees, then actually nothing changes, so long as "on the left" means "strictly on the left".
  • So for every choice of S count how many trees lie on the left of the line from S to T. This works fine for the "small" case, but for each tree it's an O(N^2) algorithm (test for each S, and then test all other trees) so O(N^3) overall, and so too slow for the "large" case.
  • Imagine fixing the tree we're interested in. What we really want to do is consider the half planes which are formed by a line passing through this tree, and count the minimum number of trees which are (strictly) in the half plane, as the line rotates. Note that the count is minimum when the line passes though another tree, so there are only finitely many cases to consider.
  • So if we compute the angles of all the other trees from our tree, then we want the minimum number of angles in an interval of length \( \pi \). We can find this in O(N) time by what I think of as a "moving window" algorithm which passes over a sorted list of angles. So the slowest part is sorting the list (I guess a bucket sort could make this fairly fast, but not in Python). In Python, this is just about quick enough.
  • Have to remember round-off error, so build an epsilon into the inequalities. It would also be possible to work directly with vectors, but the bookkeeping became too messy for me to be bothered with.

The 2D geometry we need: given vectors x=(x_1,x_2) and y=(y_1,y_2) consider the line from x to y extended in either direction. Then a point z=(z_1,z_2) is on the strict left of this line if and only if \[ (y_2-x_2) (z_1-x_1) < (y_1-x_1) (z_2-x_2). \] To see this, I'd argue as follows. Firstly translate x to 0, so subtract x from y and z. Then I want to apply an orientation preserving linear map to move y to the y-axis. This is given by e.g. the matrix \[ \begin{pmatrix} 0 & 0 \\ y_1 & y_2 \end{pmatrix} \] as this matrix has positive determinant (so is orientation preserving) and \[ \begin{pmatrix} y_2 & -y_1 \\ y_1 & y_2 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = \begin{pmatrix} 0 \\ y_1^2 + y_2^2 \end{pmatrix} \] so on the positive y-axis. Then z is mapped to \[ \begin{pmatrix} y_2 & -y_1 \\ y_1 & y_2 \end{pmatrix} \begin{pmatrix} z_1 \\ z_2 \end{pmatrix} = \begin{pmatrix} y_2z_1 - y_1z_2 \\ y_1z_1 + y_2z_2 \end{pmatrix} \] and this is on the left if and only if \( y_2z_1 - y_1z_2 < 0 \).

Categories
Recent posts