Browse Category

Hotseat

Balloon Battle (Hotseat: UKIEPC 2017, Part 1)

Overview

The United Kingdom and Ireland Programming Contest (UKIEPC) 2017 took place a few weeks ago. I used to participate semi-actively and had a rather annoyingly consistent habit of finishing in third place at Imperial. I haven’t done contest programming for quite a good amount of time, though some of my experience from interviewing candidates at Palantir might have helped.

Teams are given five hours to solve somewhere from eleven to thirteen problems. These problems involve submitting a program (the source will do) to an online judge, which typically runs said program against multiple test cases and evaluates the output of the user’s program in some way. This can entail simply checking strings, or alternatively checking if the given solution achieves some task (consider problem D in this set).

This time round I managed to figure out 9 problems, rather coincidentally with a total “penalty time” of 999 minutes. When teams are ranked, the number of problems solved is compared first; to break ties, teams are given penalty time, where solving a problem T minutes since the start of the contest, with F failed attempts, scores T + 20F penalty time. The penalty for failed attempts does not accrue until the relevant problem is actually solved. It’s still in one’s interest to finish solving any questions – even though it may give you arbitrary amounts of penalty time, it will not hurt your ranking. This score would have placed second at Imperial (maybe because some of the members of the usual team number 2 have graduated?) and, at time of writing, 51st out of 522 overall.

Problems

This half of my write-up (I intend to discuss this in two parts) covers what I think are the easier seven problems in the contest, in the order I tackled them. Looking at the metadata on Codeforces, there is a pretty clear drop-off after this. Interestingly, F was actually considered the hardest problem of the ones I’ve listed here (in that fewest teams solved it), but I was able to place it third in difficulty; I struggled more with D than some of the later ones, even, though mainly for implementation reasons.

C: Cued Up

Wrong answer at 9 minutes; correct answer at 18 minutes (10 minutes spent total).

Given a description of the number of snooker balls still on a table, determine the maximum number of possible points remaining to be scored. Initially any ball can be hit (it isn’t known whether the red or coloured balls are “on”), but thereafter players can’t pot 2 consecutive reds, and if a non-red is potted and reds remain on the table, the next ball potted must be red. Assume that only one ball is potted per shot.

This is mainly a straightforward implementation – the main snag is that if you have only red balls, then regardless of how many there are the right answer is 1. I think I messed up the first time because I fixed this edge case (which is the last of the sample tests), but accidentally ended up printing “1” before the correct answer on all of the other tests…

I: I Work All Day

Correct answer at 13 minutes (4 minutes spent).

This was basically decoding the problem statement and figuring out that “what’s left over after repeated subtraction” refers to the modulo operator. I probably could have got this one out faster if I was still comfortable with C++.

J: Just a Minim

Correct answer at 17 minutes (4 minutes spent).

Figure out the length of a tune given the length of note values. Again, raw implementation. I’m surprised this even took 4 minutes, though that might well have been because I went through all the sample tests, and also did the “hacky” approach of hardcoding the strings. There was a slightly faster to write up solution that involved special casing 0, and then writing 1/x for the others. I also might have wasted some time because I was concerned about floating point rounding errors and so calculated things in terms of sixteenths. (That’s not needed because these numbers have exact binary representations, and the problem limits would be very unlikely to result in a loss of precision.)

F: Flipping Coins

Correct answer at 26 minutes (8 minutes spent).

You have n coins, all initially tails up, and k coin flips which you are obliged to exercise – but you can choose which coin to flip. At the end of the game you keep all coins that are heads up. What’s the expected number of coins you can keep (with optimal play)?

This one is figuring out the right strategy (pretty simple – always flip something that’s tail side up if you can) and then writing a recurrence relation. There are overlapping subproblems, so a quick bit of memoisation is needed, but it is not hard to implement. I’m surprised how much candidates appeared to struggle with this problem. I guess it requires a little bit more familiarity with thinking in terms of probabilities, which has tended to be one of my stronger points at contests like these.

D: Deranging Hat

Wrong answers at 50, 53, 61 minutes. Correct answer at 89 minutes (63 minutes total spent).

A sorting network consists of comparators; given two indices i and j (importantly, in that order), if i is greater than j, then the letters at those indices are swapped. Given a string, build the sorting network that would “sort” the traditionally sorted version of that string back into the original string. For example, given the string “dude”, you would need to transform “ddeu” to “dude”, perhaps by comparing 4 and 2 and swapping them, and then 3 and 4 (and then swapping them). The sorting network can’t be more than ~10X the length of the string, in the worst case.

It took me quite a while to figure out what the problem statement meant. I came up with a reasonable idea (swap each letter into its right place, iterating through the string once), but was needlessly worried about performance and started doing a lot of fiddly book-keeping with Maps of SortedSets; there was a difficult-to-trace bug in there. I then gave up some time after 61 minutes and reimplemented things with a much simpler temporary char-array solution, which worked.

A: Alien Sunset

Correct answer at 104 minutes (15 minutes spent).

Given day lengths on multiple planets and times of sunrise/sunset, find the first time within a given time window where it is dark everywhere.

I avoided this at first because it looked like an Interval Tree kind of problem. Though seeing that many people solved it, I had a closer look and it looked like writing something in O(planets * allowed time window) would work. Thus, simply start from 1 and test each possible time interval to see if it is indeed dark everywhere, and if it is return. There was a bit of a snag with some planets having daylight hours crossing zero, but nothing too difficult to manage.

E: Education

Correct answer at 140 minutes (36 minutes spent).

A school has N departments, each with some number of students Si; they need to move to a new set of buildings, which each have capacity Ti and cost Ci (but they cannot share buildings). Minimise the total cost of all buildings, while fitting all of the students in (if possible).

I figured to sort the departments in descending order of size and then thought of some kind of dynamic programming based solution. I then realised I could do better; a greedy solution which picked the cheapest available building could actually work, if one was considering departments in descending order of size. This led rather quickly to one possible solution: sort the departments in descending order of size, and then populate a priority queue (highest priority = lowest cost) with permissible buildings. As larger departments are housed, smaller buildings can be added to the permissible pool, though we still want to ensure that large but cheap buildings would be used first. If the queue ever ran dry, the assignment would be impossible.

Five problems remain that are somewhat more difficult (at least in my opinion).

Thoughts

There are certain skills that I’m still reasonably comfortable with, like mathematics in terms of computation. There are others like computational geometry that I don’t remember too well (as we’ll see in part 2). The first part of these contests is typically a speedy rush to get credit for as many problems as possible; usually somewhere between the 5 and 7 problem mark things slow down a bit. The second part for me tends to be more interesting, though I find that the focus changes from speed to actually thinking hard about algorithms – and very often fretting over implementation as well.

Unwinding Logical Threads (Hotseat: WPF Puzzle GP 2017, Round 1C)

Background

The World Puzzle Federation is an international organisation which, among other things, organises annual puzzle contests. These involve solving puzzles that rely on logical deduction and observation. That said, maybe because I’m pretty new to these, sometimes backtracking algorithms are the order of the day!

The Puzzle GP is a series of distributed puzzle competitions run throughout the year. The GP is split into three series: C, B and A (in increasing order of difficulty). Puzzles in group C are likely to be largely accessible to general audiences (and that’s what I’m covering today); group B puzzles are typically drawn from a selection of “well-known” puzzle types, and group A puzzles often feature extensions of group B puzzles in unusual ways.

Contestants are given 60 minutes for each set of puzzles. I have very little experience with these puzzles, so I think I’ll start with group C.

(The puzzle set can be found here.)

Performance

I started off with the Darts puzzles, for which I had a strategy in mind. I then struggled with the Matches puzzles, only solving C7, before moving on to the Arithmetic Squares, both of which were solved quickly. I then spent probably a good ten minutes digging through the Word Search. I finished the easy Scrabble task and almost finished the harder one, though I failed to see a simple move near the end of the puzzle. I then started on Products, which I probably should have prioritised more highly as I think I figured out the mathematical logic behind it. I solved the 120-pointer C18 after the contest, and it was actually not too hard. With three minutes left to go after finishing C17, I took a stab at the Fill in the Blank series and managed to solve two of them.

I solved the remaining puzzles after the time ran out, apart from C3. Elastic Bands was actually very easy. I have a bit of an aversion to spatial reasoning puzzles, but recognised the problem as graph isomorphism and had some techniques for it based on that. Old Maid was also easy; I didn’t get round to it in time. The last Fill in the Blank and both instances of Count the Shapes both gave me headaches.

Selected Problems in Depth

C5-C6: Darts

Given a dartboard which has several regions with k point values and m darts, find a way to throw the darts on the dartboard such that the darts add up to a target value. Each dart must score, and each region can have only up to 1 dart. For example, with regions [4, 21, 8, 11, 13], two darts and a target of 19, the correct answer is [8, 11].

To solve this for two darts, one good solution could be to iterate through the list. On a computer, using a hash-set could be a good solution; when we look at a number, if it’s in our “target set” we’re done – otherwise we add the number we would need to make up the target to the target set. It’s a simple O(n) solution.

I think implementing a hash set on paper for me would be too troublesome. There’s an alternative which I used: sort the array in O(n \log n) and then, use a pair of pointers, one starting at the beginning and one at the end of the array. Adding the numbers up, if we’re over the target we bring the pointer at the end back, and if we’re under the target we push the pointer at the start forward.

The problem had three darts; I simply picked the overall largest number and solved the appropriately reduced target with the two-dart algorithm above, backtracking where needed to smaller largest numbers. Binary insertion sort is probably pretty reasonable to do by hand.

C10: Elastic Bands

Given a network with nodes marked with letters, and another network with edges provided, give a labelling of the nodes such that the networks are identical. This is basically finding what’s called a graph isomorphism in discrete mathematics.

I didn’t solve this in the contest, but probably should have. I split the nodes by degree, and then tried to identify relationships between these. For example, there was a single degree 4 node in the puzzle that wasn’t connected to any of the other degree 4 nodes, so I was able to uniquely identify it quickly.

C16-C18: Products

Given an N \times N grid, place the numbers from 1, 2, \ldots, 2N in the grid once each. Each row and column must contain two numbers, and numbers cannot share a cell. Clue numbers are given by the side of the grid and sometimes on diagonals. Where given, the product of numbers in the relevant row, column or diagonal must equal the clue.

The first two puzzles had N=10; the third had N=15. I think my main strategy here involved searching for prime factors that would uniquely identify numbers along the rows and columns. For N=10 this would be [11, 13, 17, 19]; for N=15 this included [17, 19, 23, 29]. I also usually started looking for very large numbers (because they might have a unique factorization in the allowed range) or small ones (e.g. in the first puzzle, there was only one column and one row with a product less than or equal to 20, implying that the 1 had to be in that column/row).

I also considered the places where a given number might fit, and in the later puzzles noticed when multiple columns could definitively use certain numbers. For example, if 5 was already used in an N=10 puzzle, and there were two 20 row hints, I could eliminate 1, 20, 2 and 10 from consideration for the other rows.

This wasn’t too difficult, though I can imagine that puzzles with only partial hints might be substantially more challenging!

Meta-Analysis

A score of 262 would have placed 12th out of 215 contestants (2nd out of 139 for contestants not in higher divisions). To be fair, this is in part because many top solvers don’t participate in the division C contests at all. Some of this might also be because there would have been less pressure as I was doing this on my own, not as part of a real contest.

Looking at the top end of the scoreboard, the Darts, Arithmetic Square, first instance of Matches and first instance of Products were solved by most of the leaders. Elastic Bands and Old Maid (I didn’t solve either of these two), as well as the Word Search were also fairly common. Thereafter, contestants varied quite a bit in what they solved. As might be expected, the contestants that solved the final instance of Products generally did very well (it was worth 120 points by itself).

Elevation (Hotseat: STEP I 2015)

Background

STEP (short for Sixth Term Examination Paper) is a somewhat difficult Maths exam that is used by several UK universities (including Cambridge, Warwick and Imperial) as part of a conditional offer for courses in Mathematics and Computer Science. A part of my conditional offer for Imperial included a 2 in any STEP paper of my choice, though it was paired with a relatively awkward 35 points for IB – perhaps because the rest of my portfolio was pretty strong.

There are three papers – I, II and III; III includes A Level Further Mathematics content, while I and II remain within the A Level Mathematics syllabus. I is also somewhat easier than II; that said, I think both papers exist because Cambridge does sometimes want students who didn’t take Further Mathematics to get a pair of grades in these exams. Nonetheless, STEP I itself is certainly no pushover. Students are graded on a scale of S, 1, 2, 3, U; the 2015 STEP I paper had 73.1 percent of students scoring at least ‘3’ (the lowest pass grade), and just 42.6 percent scoring at least ‘2’ (the lowest grade many universities would consider). This may be compared with A Level mathematics in 2015, where the analogous metrics of A*-E and A*-C respectively are 98.7 and 80.8 percent; and this is even before we factor in selection bias.

Each paper consists of 13 questions, but candidates are only required to pick six of them; their highest-scoring six questions will be used to determine their final score. Questions have equal weight (and each is marked with integers out of 20, which seems suspiciously similar to how I’ve seen this done at many universities!). Eight of the 13 questions are classified as “pure mathematics” and include tasks testing concepts like calculus, trigonometry, algebraic manipulation, series and even number theory. Three are classified as “mechanics”, typically requiring calculations on Newtonian mechanics, and two as “probability and statistics”. I almost always do 4/0/2 or 3/1/2. Note that it is possible to attempt seven or even more questions as a form of “insurance”, though given the strict time constraints this is likely to be difficult.

Performance

I had a fairly decent run, picking up 114 out of 120 points; mainly losing these to minor slips/cases where an important statement was not explicitly asserted, and a good chunk in question 7 with not clearly handling a case which was expected to be shown to bear no fruit (I thought it was rather obvious that it was not needed, and dismissed it in one line).

The last row indicates the order in which I attempted the problems; it seems this was generally consistent with how long I actually took on them (problems 2 and 13 were fast; 1 and 8 were somewhat in-between, and I struggled for a bit with 12 and messed up 7 while using up a fair bit of the time). Note that the “break-even” time if one wants to answer all questions would be 30 minutes per question.

Selected Problems in Depth

Problem 8: Series Division

First, prove that 1 + 2 + \ldots + n = \frac{n(n+1)}{2} and (N-m)^k + m^k is divisible by N. Then, consider

S = 1^k + 2^k + 3^k + \ldots + n^k

Show that if n is a positive odd integer, then S is divisible by n, and if n is even then S is divisible by n/2. Show further, that S is divisible by 1 + 2 + 3 + \ldots + n.

The two lead ins were simple. Induction does work but in both cases there were much better methods that could be used (write the series twice and pair terms up, and then pair terms in the binomial expansion). Later parts involved pairing S with a zero term, but the general theme of “pairing terms” persisted throughout the question. I think the toughest part of this one was, knowing that one had to show divisibility by \frac{n(n+1)}{2} at the very end, figuring out that it was safe to split this into two terms and show them separately. This works because the highest common factor of n and n + 1 is 1. My number theory was a bit rusty so I wasn’t sure if that was correct, and proved it during the paper.

Problem 12: On Fish Distributions

The number X of casualties arriving at a hospital each day follows a Poisson distribution with mean 8. Casualties require surgery with probability 1/4. The number of casualties arriving on each day are independent of the number arriving on any other day, as are the casualties’ requirements for surgery. (After some initial work) Prove that the number requiring surgery each day also follows a Poisson distribution and state its mean. Given that in a particular random chosen week 12 casualties require surgery on Monday and Tuesday, find the probability that 8 casualties require surgery on Monday (as a fraction, in its lowest terms).

This one really wasn’t too bad, though it involved a lot of algebraic manipulation and it seems I took quite a long time on it when doing the paper. Essentially, the independence condition should hint that if we have X casualties, the probability of S needing surgery is clearly binomially distributed. X itself is a random variable, but that’s fine; the law of conditional expectation gives us

P(S = s) = \displaystyle \sum_{t = s}^{\infty} P(S = s | X = t) P (X = t)

and a suitable substitution yields this:

P(S = s) = \displaystyle \sum_{t = s}^{\infty} \left( \frac{t!}{s! (t - s)!} \times \left( \frac{1}{4} \right)^s \times \left( \frac{3}{4} \right)^{t-s} \times \frac{e^{-8} 8^t}{t!}\right)

After some fairly involved algebraic manipulation, one can indeed recover a Poisson form for the pdf of S. Using this, the last part is relatively simple actually; we want P(S_1 = 8 | S_1 + S_2 = 12) and relying on the fact that a sum of independent Poissons is Poisson itself (so the means of S_1 and S_2 are 2 each gives us that the mean of S_1 + S_2 is Poisson, and with mean 4).

Problem 13: Probability and State Machines

Already covered in a previous post. I dispatched this one very quickly, though I was already familiar with the Markov process model that I used here.

Meta-Analysis

The main datasource we have available here is an Examiner’s Report that discusses to some extent what happened (though we don’t have full details). The grade boundary for an S is 96, so a 114 is comfortably in that range; 3.5 percent of candidates scored that. Question-level data isn’t published beyond the comments in the Examiner’s Report.

Focusing on the questions that were attempted, my opener Q1 which was a test of curve-sketching was also the highest-scoring question on the paper, with students scoring an average mark of over 13.5 (with caveats that some students were worried about curve sketching and thus avoided it). This was the second “easiest” question as far as I was concerned.

The other pure maths questions I attempted (2, 7 and 8) were also popular, and attempted with varying degrees of success (questions 2 and 7 were the second and third highest scoring questions). Probability and Statistics for some reason seems to always cause issues for students attempting these papers, with mean scores in the 2-3 range, though having done Olympiads in the past (and specialising in combinatorics and probability) I understandably found these easier.

Generally, STEP I for me tends to be fairly tough but certainly comfortable, II is solidly difficult, and doing III often makes me feel like a dog behind a chemistry set (“I have no idea what I’m doing”), especially since I didn’t take Further Maths in high school.

Running the Gauntlet (Hotseat: OCR Mathematics C1-C4)

Background

The GCE A Level is a school-leaving qualification that students in the UK take at the end of high school. Students usually take exams for 3-4 subjects. The exams are graded on a scale from A* to U (though not with all characters in between); typically an A* is awarded to the roughly top 8-9 percent of students.

This is a rather different type of challenge – previous installments of this series have featured especially difficult exams (or rather, competitions; only the MAT is realistically speaking an exam there). I’ve usually struggled to finish in the time limit (I didn’t finish the AIME and barely finished the MAT; I had some spare time on the BMO R1, but still not that much). I could of course do this in the same way as the other tests, though the score distribution would likely be close to the ceiling, with random variation simply down to careless mistakes.

Interestingly, the UK has multiple exam boards, so for this discussion we’ll be looking at OCR, which here stands not for Optical Character Recognition, but for Oxford, Cambridge and RSA (the Royal Society of Arts). The A level Maths curriculum is split into five strands: core (C), further pure (FP), mechanics (M), statistics (S) and decision (D); each strand features between two and four modules, which generally are part of a linear dependency chain – apart from FP, where FP3 is not dependent on FP2 (though it still is dependent on FP1). For the Mathematics A level, students need to take four modules from the core strand, and two additional “applied” modules; Further Mathematics involves two of the FP strand modules plus any four additional modules (but these cannot overlap with the mathematics A level ones). Thus, a student pursuing a Further Mathematics A level will take 12 distinct modules, including C1 – C4 and at least two FP modules, for example C1-4, FP{1,3}, S1-4, D1 and M1.

(In high school I took the IB diploma programme instead, which did have Further Mathematics (FM), though I didn’t take it as I picked Computer Science instead. That was before Computer Science became a group 4 subject; even then, I think I would still have wanted to do Physics, and thus would not have taken FM in any case.)

Setup

I attempted the June 2015 series of exams (C1 – C4). Each of these papers is set for 90 minutes, and is a problem set that features between about seven and ten multi-part questions. The overall maximum mark is 72 (a bit of a strange number; perhaps to give 1 minute and 15 seconds per mark?). To make things a little more interesting, we define a performance metric

P = \dfrac{M^2}{T}

where M is the proportion of marks scored, and T is the proportion of time used. For example, scoring 100 percent in half of the time allowed results in a metric of 2; scoring 50 percent of the marks using up all of the time yields a metric of 0.25. The penalty is deliberately harsher than proportional, to limit the benefit of gaming the system (i.e. finding the easiest marks and only attempting those questions).

Most of the errors were results of arithmetical or algebraic slips (there weren’t any questions which I didn’t know how to answer, though I did make a rather egregious error on C3, and stumbled a little on C4 with trying to do a complex substitution for an integral, rather than preprocessing the term). There are a few things I noted:

  • The scores for the AS-level modules (C1, C2) were considerably higher than that for the A-level modules (C3, C4). This is fairly expected, given that students only taking AS Mathematics would still need to do C1 and C2. Furthermore, from reading examiners’ reports the expectation in these exams is that students should have enough time to answer all of the questions.
  • The score for C1 was much higher than that for C2. I think there are two reasons for this – firstly, C1 is meant to be an introductory module; and secondly, no calculators are allowed in C1, meaning that examiners have to allocate time for students to perform calculations (which as far as I’m aware is something I’m relatively quick at).
  • The score for C4 was actually slightly higher than that for C3 (contrary to a possibly expected consistent decrease). While there is meant to be a linear progression, I certainly found the C3 paper notably tougher than that for C4 as well. That said, this may come from a perspective of someone aiming to secure all marks as opposed to the quantity required for a pass or an A.

We also see the penalty effect of the metric kicking in; it might be down to mental anchoring, but observe that perfect performances on C1 and C2 in the same amount of time would have yielded performance numbers just above 5 and 3, respectively.

Selected Problems in Depth

C3, Question 9

Given f(\theta) = \sin(\theta + 30^{\circ}) + \cos(\theta + 60^{\circ}), show that f(\theta) = \cos(\theta) and that f(4\theta) + 4f(2\theta) \equiv 8\cos^4\theta - 3. Then determine the greatest and least values of \frac{1}{f(4\theta) + 4f(2\theta) + 7} as \theta varies, and solve the equation, for 0^{\circ} \leq \alpha \leq 60^{\circ},

\sin(12\alpha + 30^{\circ}) + \cos(12\alpha + 60^{\circ}) + 4\sin(6\alpha + 30^{\circ}) + 4\cos(6\alpha + 30^{\circ}) = 1

This might have appeared a little intimidating, though it isn’t too bad if worked through carefully. The first expression is derived fairly quickly by using the addition formulas for sine and cosine. I then wasted a bit of time on the second part by trying to be cheeky and applying De Moivre’s theorem (so, for instance, \cos(4\theta) is the real part of e^{i(4\theta)} which is the binomial expansion of (\cos \theta + i \sin \theta)^4), subsequently using \sin^2 x = 1 - \cos^2 x where needed. This of course worked, but yielded a rather unpleasant algebra bash that could have been avoided by simply applying the double angle formulas multiple times.

The “range” part involved substitution and then reasoning on the range of \cos^4\theta (to be between 0 and 1). The final equation looked like a mouthful; using the result we had at the beginning yields

f (12 \alpha) + 4 f (6 \alpha) = 1

and then using a substitution like \beta = 3 \alpha, we can reduce the equation to 8 \cos^4 \beta - 3 = 1. We then get \cos \beta = \pm \left( \frac{1}{2} \right)^{(1/4)} and we can finish by dividing the values of \beta by 3 to recover \alpha.

C4, Question 6

Using the quotient rule, show that the derivative of \frac{\cos x}{\sin x} is \frac{-1}{\sin^2x}. Then show that

\displaystyle \int_{\frac{1}{6}\pi}^{\frac{1}{4}\pi} \dfrac{\sqrt{1 + \cos 2x}}{\sin x \sin 2x} = \dfrac{1}{2}\left(\sqrt{6} - \sqrt{2}\right)

The first part is easy (you’re given the answer, and even told how to do it). The second was more interesting; my first instinct was to attempt to substitute t = \sqrt{1 + \cos 2x} which removed the square root, but it was extremely difficult to rewrite the resulting expression in terms of t as opposed to x. I then noticed that there was a nice way to eliminate the square root with \cos 2x = 2 \cos^2 x - 1. The integrand then simplifies down into a constant multiple of \frac{-1}{\sin^2x}; using the first result and simplifying the resultant expression should yield the result. That said, I wasted a fair bit of time here with the initial substitution attempt.

Meta-Analysis

To some extent this is difficult, because students don’t generally do A levels in this way (for very good reasons), and I’m sure that there must be students out there who could similarly blast through the modules in less than half the time given or better (but there is no data about this). Nonetheless, the A level boards usually publish Examiners’ Reports, which can be fairly interesting to read through though generally lacking in data. The C3 report was fairly rich in detail, though; and the 68/72 score was actually not too great (notice that “8% of candidates scored 70 or higher”). Indeed the aforementioned question 9 caused difficulties, though the preceding question 8 on logarithms was hardest in terms of having the lowest proportion of candidates recording full marks.

The University Gatekeepers (Hotseat: MAT 2013)

Background

I didn’t have to take the Mathematics Admission Test when I applied to Imperial (though the Cambridge STEP was a part of the conditions of my offer, probably because I didn’t take FM). This was added as a part of the admission process in 2013, though seemingly only for students aiming to read Mathematics. Oxford has been running this test for fairly long, and they use it both for Mathematics as well as Computer Science. Unlike STEP, candidates don’t get a choice of questions, but instead are prescribed questions based on the programme they’re applying to.

The paper has seven questions and candidates need to answer five. All candidates have to answer question 1, which is actually ten multiple-choice questions worth 4 marks each (no penalties for guessing). There are then six 15-mark questions that follow. Candidates in Computer Science generally have two questions that the broader Mathematics population also takes – in 2013 this featured an algebra question on functional equations, and a discrete mathematics/combinatorics question. There are two further questions, one of which tends to incorporate a significant element of mathematical logic (2013’s problem revolved around the notion of common knowledge, much like the infamous Cheryl’s birthday question), and another that deals with formal languages and reasoning about similar structures (the 2013 problem focused on an inductively generated language).

I did the Computer Science stream of the paper, and managed to put together a score of 95 (40 on the first problem; 14 on Q2, 15 on Q5, 15 on Q6 and 11 on Q7) owing to a lucky (or, depending on how you see it, educated) guess on one of the multiple-choice problems. The “Mathematics-only” questions Q3 and Q4 didn’t seem any harder, though; I cleared both of them without much difficulty (whereas Q2 was somewhat nastier, in general). I lost the points on Q7 owing to a careless error; specifically, that if an expression Bw is reversed, the resultant expression is certainly not wB (well, unless w is palindromic!)

The specific paper I did is here.

Selected Problems in Depth

Problem 1: The Gauntlet

I don’t find multiple choice questions to play very well with mathematics, because it’s very often possible to reverse engineer a solution or otherwise arrive at the correct answer via an unexpected solution path. For example, consider problem G:

p_n(x) = (x - 1) + (x - 2) + \ldots + (x - n)

What is the remainder when p_n(x) is divided by p_{n-1}(x)?

Presumably, the intended solution path was to express p_n(x) in a more convenient form (noting the arithmetic progression in the constant terms) and then actually do the division. However, given the options, it sufficed to simply test it for p_3(x) and p_2(x), noting that the result of the division was negative, and that only one of the options was negative.

Nonetheless, there were certainly ample opportunities for trick questions (this paper had E, where there was a trap with an algebraic expression easily being bounded by degree 7, though it wasn’t the case that it actually was degree 7).

I got through 9 of the problems fairly smoothly, though struggled with H (failing to realise that one of the equations was actually that of a semicircle, and plowing into aggressive trigonometry-based integration). In the end I ran out of time towards the end of the integration, but I guessed the only option that featured the subtraction of the area under one of the lines, which turned out to be correct.

Problem 2: Functional Equations

This was generally fairly straightforward till the end, where the task was to find some function f that satisfied f(t) - f(1-t) = (2t - 1)^3. In hindsight it seemed fairly obvious to conclude that a good way of solving this would be to treat f as a cubic polynomial, though I struggled for a while substituting random values of t in to the functional equation to see if anything dropped out. I then went through some messy reasoning along the lines of “the difference between two points increases cubically as the (x-)distance between said points increases linearly, so the derivative is probably quadratic, thus the function is probably cubic”. I then established f(t) = At^3 + Bt^2 + Ct + D and was on my way after a modest algebraic bash.

Problem 6: Reasoning about Knowledge

This question introduces Alice, Bob and Charlie; Charlie writes a (different) number on Alice and Bob’s foreheads. Thus Alice and Bob can see the other’s number, and Charlie can see both. The question begins with a little warm-up to prompt candidates into thinking about epistemic reasoning (if Alice knows her number right off the bat, it must be 2 – because she can see Bob’s 1; for any other number she wouldn’t be able to know). Things heat up a little later on:

  • Charlie: Your numbers are between 1 and 10 inclusive.
  • Alice: I don’t know my number. Is my number a square number?
  • Charlie: If I told you, you would know your number.
  • Bob: I don’t know my number.

What is Alice’s number?

We start by noting that the squares are 1, 4 and 9. Since Alice can see Bob’s number, she already knows that her number is one of two possibilities, spaced two apart. For Charlie’s statement to make sense, exactly one of the possibilities has to be a square. This tells us that Bob’s number is 2, 3, 5 or 8. (It couldn’t be 10, because if it was Alice would know that her number is 9.)

Next, Bob can see Alice’s number, but doesn’t know his. Since he can see Alice’s number, Alice’s number A must be one for which both A + 1 and A - 1 are candidates. This gives us the answer: her number has to be 4.

This one, in my opinion, stopped at a fairly early level; things could develop a fair bit more. However, assuming proportional time weighting (and bearing in mind that I did write my thesis on epistemic logic) the 22.5 minutes candidates were given for this is reasonably challenging.

Synthesis

I found STEP to be somewhat more demanding, perhaps because it had questions that focused more on depth rather than breadth, and also because I took the computer science stream of the paper while STEP just focuses on mathematics.

The average score of all candidates on questions 1 through 5 was 44.8, with 60.6 for successful applicants. Nonetheless, I subsequently worked through problems 3 and 4 and actually found them considerably easier than 2. Interestingly, there was a candidate who scored between 85 and 89 but was nonetheless rejected; also, no one scored 100, which seems surprising (this would certainly have been possible if not for the careless slip I made on problem 2 – or maybe the marking for some aspects such as the rigor demanded in proofs was stricter than my own marking).

This was quite enjoyable, actually. I’m not sure how I would have fared had I taken this exam in the past! I’d think that my knowledge of logic, as well as the more computer-science oriented topics (discrete mathematics and formal languages) would have improved, though knowledge of say calculus or analysis probably would be slightly weaker than when I finished high school.

Playing with Blocks (Hotseat: British Informatics Olympiad R1, 2015)

Second in a series. I apologise for the temporary hiatus, had a couple of weeks travelling and then intense sessions at work (part of this was my choice, but still).

Background

I was not in the UK for high school, and studying computing/informatics wasn’t common in my high school in Singapore either. I never actually participated in the British Informatics Olympiad. This is the UK’s national high-school competition in computing, and unlike normal programming contests there’s an explicit portion involving reasoning and discrete mathematics which I like. This can get intense; problems especially in the second round can feature fairly complex reasoning – such as 2009’s second round which required understanding models of computation in FRACTRAN (and eventually deciphering a “program” that computed the Fibonacci series). For quite a few contest problems, intuitively determining a solution, or even being uncertain but firing it off anyway in hopes of getting it accepted is much easier than trying to prove that the solution is correct.

The first round is somewhat less intense, but still has plenty of opportunities for interesting problems. There are typically three tasks; the first is gentle and meant to be a warm-up, the second tests implementation (perhaps more like what I might expect on a programming exam in university) and the third tests algorithms (in a sense, more like a standard contest problem). Each question has most of the points (about 75%) allocated to implementation and the remainder to several “reasoning” questions. Partial scores are awarded for solutions that aren’t optimal or fail on some cases (much like in the IOI, though the information is not known to the students).

This was one of the easier papers I’ve done; I worked my way through the tasks very quickly, and didn’t have too much of a problem (other than a careless error in problem 2). Most of the time I score above 90 points on these, though sometimes if I don’t “get” problem 3 in an optimal way or make subtle errors on problem 2 the score will be a fair bit lower.

The specific paper I did is here.

Problem 1: Block Palindromes

Given a string, find the number of ways of decomposing it into at least two blocks such that when the blocks are reversed (but not the letters within the blocks), the arrangement of blocks looks the same. For example, BARBAR is a block palindrome, since (BAR)(BAR) reads the same forwards and backwards. Of course, every ordinary palindrome is also a block palindrome, since taking one-letter blocks is allowed.

Not too much here; the problem is readily amenable to a simple recursive implementation (try taking each block length from 1 to half the string length and see if the string ends with that prefix – if so, recurse and add that result to our total). It would be possible to use memoisation to improve performance here, since there can be repeated subproblems e.g. with AABCBAA, you would be solving for the number of solutions to BCB twice. However, given the small constraints (strings of up to 10 characters) this wasn’t needed.

This problem probably had one of the trickier reasoning questions though – if all groupings of a block palindrome contain an even number of blocks, how many groupings can there be (and why)?

I attacked this one with a proof by contradiction – that it is not possible to have any groupings

S = B_1 B_2 \ldots B_{n-1} B_n B_{n-1} \ldots B_2 B_1

for n \geq 2. This can be shown by construction:

S' = (B_1) (B_2 \ldots B_{n-1} B_n B_{n-1} \ldots B_2) (B_1)

is a valid decomposition, which has three blocks. Of course, the empty string isn’t a valid block, so we require S = B_1 B_1 and the number of groupings has to be 1. We can probably formulate an even stronger condition (for instance, that apart from B_1 itself, no prefix of B_1 is also a suffix of B_1). While the reasoning seemed sound to me, I wasn’t too confident I had the right answer here.

(Note: The question text implied that a block palindrome could be decomposed into blocks in some way, so while 0 satisfies “all groupings” it wouldn’t be a block palindrome.)

Problem 2: Battleships

Given a funky (deterministic) algorithm for generating random numbers, implement it, and use it to fill a grid with ships of certain sizes via some kind of rejection sampling. The key constraints are that the grid has a finite size, and more interestingly ships are not allowed to touch (even diagonally).

Implementing the random-generator is pretty much following instructions from the spec. However, there are several ways to implement the latter constraint. Given that optimality is generally not important in problem 2, I went for a rather nasty solution that, say, for a k-ship placed horizontally would iterate through a 3 \times (k + 2) bounding rectangle around the ship and mark all those squares as unusable. Better asymptotic complexity can probably be obtained using an R-tree (though that is probably not reasonable for contests – especially without a reference!).

There was a rather nasty “reasoning” problem about the number of ways to place ships of size 4, 3, 2 and 1 on a 5 by 5 grid – this was also where I lost the five points. I hacked my implementation to, instead of using the random number generator, simply use backtracking to count the number of possible placements. However, I forgot that my bounding rectangle system was based on booleans (in other words, a square that was unusable because of two different ships would suddenly become usable after just one was removed), and thus came up with the impressive total of 427,840 possibilities (correct answer: 1,424)!

I subsequently fixed the aforementioned bug (using integers instead) and confirmed that the answer was indeed 1,424. During the test I did try smoke-tests that verified that a 1-ship could be placed in 25 ways and a 5-ship in 10; I attempted to do two 1-ships, but decided that I would have had too much pain working through the combinatorics for that.

Problem 3: Modern Art

This problem revolved around (reasonably) efficiently determining the ith permutation of a string in terms of lexicographic ordering, possibly involving duplicate characters. For example, in a string which consists of five As, Bs, Cs and Ds – what is the 11,223,344,556th permutation?

Of course, for smaller strings and smaller numbers it would suffice to implement some kind of next-permutation generator. This is a pretty standard algorithm. We can then step through the permutations until we get what we want – and there are some test cases that would be solvable with this; you would get (I think) 11 of the 25 points available.

The key idea is that we don’t want to explore all of the permutations. From combinatorics, we can quickly calculate the number of permutations of five As, Bs, Cs and Ds:

\displaystyle {20 \choose 5} \times {15 \choose 5} \times {10 \choose 5} \times {5 \choose 5} = 11,732,745,024

Intuitively, we are close to the “end”; we can thus be pretty sure that our 11-millionth permutation should start with a D. We can thus write a recursive (or iterative) algorithm that identifies the first character based on this search.

I began by implementing a function that computes the number of ways of permuting a given number of As, Bs, Cs and Ds. This was done in a bit of a hacky way and has some (probably unnecessary) memoisation.

private static long numPerms(long as, long bs, long cs, long ds) {
  List<Long> longs = Lists.newArrayList(as, bs, cs, ds);
  Collections.sort(longs);
  if (cache.contains(longs)) {
    return cache.get(longs);
  }
  long totalChars = as + bs + cs + ds;
  long perms = 1L;

  // Computes (total C l) then updates total
  for (Long l : longs) {
    long num = 1;
    long denom = 1;
    for (int i = 0; i < l; i++) {
      num *= totalChars - i;
      denom *= i + 1;
    }
    perms *= num / denom;
    totalChars -= l;
  }

  cache.put(longs, perms);
  return perms;
}

Interestingly, it turns out it would actually have been okay to build the entire numerator and denominator and then divide the two; perhaps 20 was chosen to avoid complications with overflow (since 21! will exceed the max value of a 64 bit integer). Anyway, the highest value the numerator could have taken on here was 1,860,480 (20 to 16 multiplied together) so I was sure I was safe this way.

We then go through the characters in lexicographic order, and for each one, consider the number of permutations that would be feasible. The general approach is something like this:

private static String getPermutation(long as, long bs, long cs, long ds, long offset) {
  if (as == 0 && bs == 0 && cs == 0 && ds == 0) {
    return ""; // we've built the entire thing
  }

  long permsCovered = as == 0 ? 0 : numPerms(as - 1, bs, cs, ds);
  if (offset < permsCovered) {
    return "A" + getPermutation(as - 1, bs, cs, ds, offset);
  }
  long permsPassed = permsCovered;
  permsCovered += bs == 0 ? 0 : numPerms(as, bs - 1, cs, ds);
  if (offset < permsCovered) {
    return "B" + getPermutation(as, bs - 1, cs, ds, offset - permsPassed);
  }
  permsPassed = permsCovered;
  permsCovered += cs == 0 ? 0 : numParams(as, bs, cs - 1, ds);
  if (offset < permsCovered) {
    return "C" + getPermutation(as, bs, cs - 1, ds, offset - permsPassed);
  }
  // and the same for D.
}

I actually finished the implementation fairly quickly, but decided to write a couple of tests; I stepped through the 12 permutations of “ABBC” as given in the spec, and also wrote a test for “AAABBBCCCDDD” that all the permutations were generated in the correct order (using numPerms to give me the range). I also of course tried a couple of edge-ish cases such as each of “A”, “B”, “C” and “D”, and a test to verify we could handle the expected scale (five of each character, retrieving the 1st as well as 11732745024th permutation).

The “reasoning” problems on this one were very easy compared to the other two questions.

Conclusion

Unfortunately meta-analysis is somewhat limited here as unlike the AIME results, the ones for the BIO aren’t public. I’m pretty sure 95 is a solid score as the contest isn’t that easy, but I won’t be surprised if there are multiple 100s (with a bit of caution I could have gotten one)!

Style during programming contests is an interesting issue. I find that many contestants especially with C++ like to use rather bespoke preprocessor routines (e.g. cin as f, cout as g). I’m actually used to some of them as well e.g. ll for long long, vpll for vector<pair<long, long>>. If one understands these it’s probably better for speed, though when debugging I find having not-unreasonable names is preferable (even if my code is written more for speed than style).

Revisiting Mathematics Competitions (Hotseat: AIME II, 2015)

I remember I had a pretty good time doing the Haskell January Test earlier this year, and thought it might be both enjoyable and useful to revisit some of these past mental exercises. Hotseat is intended to be a series that discusses my thoughts, ideas and reflections as I take or re-take examinations or competitions; many of these will end up being related to mathematics or computer science in some way, though I’ll try to also include a few that go against that grain.

Background

I didn’t actually participate in the American Invitational Mathematics Examination (AIME) as I don’t think my high school offered it (the only maths competitions I remember taking myself are the Singapore Math Olympiad and the Australian Mathematics Competition). This is typically the “second round” of the main mathematical competition in the US (the first being the AMC, and the third being the USAMO), and features 15 problems, all of which have integer answers from 0 to 999. The point of this is to facilitate machine scoring. While the questions might indeed have integer answers, they can be very difficult especially towards the end.

2015 II was supposed to be an easy paper, though I didn’t find it to be very much easier than what I recall these to be. You can find the paper here.

I managed to fight my way through 12 out of 15 questions, leaving out two hard problems towards the end and a not-so-difficult one in the middle (mainly because I struggle somewhat with geometry in three dimensions). I think I’m not used to doing these as quickly as I would have in the past as well; problem 14, for instance, would probably have taken under 15 minutes in the past while it now took 32. 8 minutes on problem 1 is rather bad, as well.

The values below indicate the time spent on each problem; here green means the problem was answered correctly while grey means no answer was given. (In practice, in a contest you would take the 1-in-1000 shot and guess, since there are no penalties for guessing!). I’ve also outlined the subject areas – you can see that I tend to be stronger with combinatorics and probability, and struggle somewhat with geometry!

I think I remember mentioning in a post a very long time ago that when I look at data, I tend to initially look for things that seem unusual. Bearing in mind that the difficulty of these papers tends to rise, we could say the 32 minutes spent on question 14 or 15 on question 7 is perhaps not too far from expectations (the target “pace” here is 12 minutes per question, if you’re trying to finish). Bearing that in mind, we can look at a couple of outliers:

  • Problems 1, 6 and 11 took unduly large amounts of time.
  • Problems 2, 3, 8 and 12 were done well above pace.

Some of these were actually pretty interesting, which is one reason I tend to enjoy these competitions as well.

Selected Problems in Depth

Problem 1: Let N be the least positive integer that is both 22 percent less than one integer and 16 percent greater than another integer. Find the remainder when N is divided by 1000.

For this question you were actually supposed to find N; the “divided by 1000” shenanigans was so that the answer would be an integer from 0 to 999. The challenge here was really formulating a requisite equation from the problem statement, which would be

\dfrac{39}{50} k_1 = N = \dfrac{29}{25} k_2

and then reasoning that N must be divisible by both 29 and 39, such that k_1 and k_2 were both integers. Since these are relatively prime N = 29 \times 39 = 1131 and the answer was 131. I guess I hadn’t really warmed up yet, and wanted to be very careful to set up the expression correctly, so this took rather long.

6 was a bash with the Vieta formulas, though my brain temporarily switched off when I somehow thought a cubic equation should have four roots. 11, on the other hand, was a rather messy geometry question which I initially found tough to visualise. The solution on Art of Problem Solving involves constructing perpendiculars from the centre of the circle to the two lines, but I didn’t think of that (and for that matter wouldn’t have known that was a property of a circumcentre), and instead had a rather painful trigonometry bash to find the answer.

On the brighter side, 2 and 3 were rather simple questions (an elementary probability question, and a rather quick modulo-arithmetic one) and I cleared them off very quickly. I dealt with 8 using some rather quick-and-dirty casework that yielded the desired result, though it wasn’t too interesting. I’d say 12 was a bit more of a fun one.

Problem 12: There are 2^{10} = 1024 possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.

I thought in terms of recurrences and dynamic programming, and realised that valid strings (in the long case) must end in BA, BAA, BAAA or their flipped versions (alternatively, with a blank space in front). To end a string with BAA, it must previously have ended with BA, and so on for BAAA. Thus, the following equations drop out:

BA(n) = AB(n - 1) + ABB(n - 1) + ABBB(n - 1)

BAA(n) = BA(n - 1); BAAA(n) = BAA(n - 1)

Since the AB and BA cases are symmetric, we can simplify the first equation above to

BA(n) = BA(n - 1) + BAA(n - 1) + BAAA(n - 1)

And we have of course the base cases; BA(1) = 1, BAA(1) = 0, BAAA(1) = 0. Computing 2 \left( BA(10) + BAA(10) + BAAA(10) \right) is then not difficult, and yields 548.

In mathematical terms I would say problem 14 required some insight, though for seasoned competitors it would probably still not have been too difficult.

Problem 14: Let x and y be real numbers satisfying x^4y^5 + y^4x^5 = 810 and x^3y^6 + y^3x^6 = 945. Evaluate 2x^3 + (xy)^3 + 2y^3.

I initially tried squaring the resultant expression, and combining the two given results in various ways. This went on for about 20 minutes with little meaningful progress. I then took a step back, attempted and finished up with problem 11, and came back to this. I suddenly had the idea of combining the two givens to force a cubic factorisation:

x^3y^6 + 3x^4y^5 + 3x^5y^4 + x^6y^3 = 810 \times 3 + 945 

And that simplifies down to

x^3y^3 (x+y)^3 = 3375 \leadsto xy(x+y) = 15 

We then proceed by factoring the first result:

x^3y^3 (xy(x+y)) = 810 \leadsto x^3y^3 = 54 

We can get 17.5 for x^3 + y^3 by factoring the second given to x^3y^3(x^3 + y^3). The final result is then just 35 + 54 = 89.

I subsequently figured out solutions for 13 (my brief intuition about complex numbers was kind of on the right track, but I didn’t have time) and then 9 (not good with 3D geometry), and had a look at the rather painful solution for 15.

Meta-Analysis

It’s worth taking a look at how this performance was relative to the actual score distribution, which is available on the AMC statistics page. A score of 12 would be in the 96.09th percentile, which is interesting; I did the 2015 AIME I a few weeks ago and scored 11, but on that contest that was the 97.49th percentile!

There’s also a report on item difficulty (i.e. the proportion of correct responses to each problem). I’ve graphed this below (items I answered correctly are in green, while those I did not are in red):

It’s interesting that problem 12, a problem I found to be one of the easier ones (assuming you sort by success and then time, I found it to be the 8th hardest) turned out to be the second “hardest” problem on the paper! I’d attribute some of this to a programming background; if I took this contest when I was in high school I think I would probably struggle with 12.

13 and 15 were hard as expected; the next hardest problem in general after that was 10 (just a notch above 12 in difficulty for me) though again it relies on tricky combinatorics. We then have 6, 11 and 8 before 14; I found 6 and 11 relatively harder as well, as mentioned above, though 8 was fairly trivial for me. It turns out that my geometry weakness is fairly real, as 9 was completed by more than half of the participants! We can also observe problem 1 being challenging relative to its location in the paper.

Conclusion

This was a good mental workout, and it felt nice to be able to hack away at the various problems as well. I think a 12 is pretty solid (the 96th percentile is that of AIME qualifiers, which itself is something like the top 5 percent of high school students taking the AMC, so that would be the 99.8th percentile – and you could argue that considering only students taking the AMC already introduces a selection bias towards those with greater aptitude). I’d probably have been able to solve 9 and maybe 15 if I was doing this back in high school, though I’m not sure I would have managed 12.

I can certainly feel a loss of speed, though I think my problem-solving ability is for the most part intact, which is good.