Browse Month

November 2017

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).

Inflation and the Substitution Effect

I sometimes pick up my groceries at Iceland (the supermarket, not the country). When I was there today, I noticed a bunch of frozen pizzas which were typically on sale at £1 now on sale at 2 for £2.50. I thus bought zero of them, opting for a substitute (that turned out to be pretty good!). This is one example of a shortcoming of the generally accepted way of measuring inflation (via a consumer price index).

Inflation refers to an increase in general prices of goods and services (in numerical terms). With the devaluation of the pound after the Brexit vote, I’ve experienced imported inflation (because a pound buys fewer dollars/yen etc., and overseas suppliers of goods want to be paid in their currency).

Of course, one problem is how one measures “general prices of goods and services”. Typically, inflation is measured via changes in a consumer price index. This is an aggregate of the prices of a supposedly representative basket of goods and services. The basket is reviewed periodically, as some goods become more (or less) frequently consumed. For example, in the UK, this is managed by the Office for National Statistics. The 2016 basket is listed here, and changes included the addition of video game downloads and removal of nightclub entry.

Of course, individuals’ spending patterns can be very different from the “average”. One can imagine a personal inflation rate that could be very different from CPI. For example, I don’t drive, so a significant increase in the price of cars might not affect me very much. (There could be some knock-on effects, e.g. if the cost of minicab rides increases.) Similarly, an increase in the cost of recreational boats (which are part of the basket) would have little impact on me. Conversely, I consume a fair amount of potatoes, so a cost increase there could have an outsize impact on me…

It probably won’t, actually. If potatoes become expensive, I will eat fewer potatoes and more rice or noodles.

Something similar actually happened after the Brexit vote. I used to enjoy an occasional instant ramen treat from the Japan Centre in London. However, with the pound falling almost 20 percent against the yen in the wake of Brexit (from 160 to about 130), prices were increased significantly. In many cases, this exceeded the 25% cost increase, perhaps because they wanted to avoid further increases if the pound fell further. GBPJPY is now about 149, but the GBP prices haven’t moved, possibly for the same reason. In any case, I’ve switched to eating more of other forms of carbohydrates.

Note that the above doesn’t always work as goods actually need to have a reasonable substitute. Medical services, (possibly imputed) rent and education come to mind. There are opportunities for geographic arbitrage here (e.g. travelling to Brazil as a medical tourist, living in an RV or attending university in continental Europe respectively), but these tend to have higher barriers to entry.

This is the key intuition behind chained CPI; it aims to account for people consuming different goods and services as prices change. This is currently being considered in the US as part of Trump’s tax reform (and would, in the future, save the government money by reducing tax bracket adjustments – chained CPI would be lower than CPI).

Of course, computing chained CPI is a hard problem. For example, there was a parasite problem in salmon farms in early 2017, causing supply to fall. (Again, this was another instance where my consumption habits changed.) Is trout an acceptable substitute? Cod? Chicken? Tofu? Any kind of food? I’d answer yes to the first and kind-of to the second. For the last three, that would probably only be the case in emergency circumstances. There were similar problems with an iceberg lettuce shortage in early 2017, and yet people continued to buy them in spite of prices almost tripling.

Furthermore, one typically only gets to witness substitution effects after the fact. If the price of lettuce triples, it’s difficult to predict how many people would switch or partially switch to substitutes. In practice, statistical offices usually come up with a preliminary estimate and then revise it when they have more data available.

As an individual who has responded to the substitution effect quite a few times, especially since I moved to the UK, I think chained CPI makes sense. For me at least, the substitution effect is real and powerful. It hasn’t received the friendliest of receptions in the US, at least in part for political reasons (it hits the poor and elderly hard, for various reasons). It does make sense to have a different metric to use for benefits or the state pension, perhaps more tailored to the relevant populations (should video game downloads, generally speaking, really go into an elderly CPI?). However, in general the chained CPI seems more accurate and I see no reason not to use it.