So, this post is a bit delayed – I actually had to do this round from a hotel room on a 13inch macbook – with no mouse. Far from ideal conditions and maybe they contributed to my just missing out on making it through to round 3. 9th placed Australian, in 543rd place. Tikitiki and Aussie got great starts this round, I think they must have seen some of these kinds of questions recently or something…
I started by reading all of the problems first, thinking maybe it would be useful to have my mind mulling them over in the background while I worked on the first problem. So my first problem submission time was not great. Second problem had me stumped for a while, but I eventually got my head on straight and realised the solution was pretty easy after all. But it only left me 30minutes to try to get one more small input. I figured I needed to go for Q3 to be safe as it seemed easier and was worth more points. It probably was a good decision, but an amazingly stupid mistake while solving an equation for x left me with code that was crashing with 2 minutes left on the clock. I realised the problem at 1minute left, but wasn’t fast enough to fix it. (Also there was one more issue which I didn’t realise until the next day, but it is possible my solution would have passed the small input tests anyway. Getting it right would have been a top 250 placing, which would have been great.)
In any case I have a nice new t-shirt, which was the only prize I was going to get… in this competition anyway…
Q1) There are ropes hanging down from points. Each rope has a given length and given position. All hanging points are at the same level, which is the same level you start at, and the same level of your destination, which is a specified location past the last rope. You start off holding the first rope. You can swing out and grab any rope in your path. Having grabbed a rope you can pull yourself back up level with the hanging points to any place between the two hanging points (limited by the length of the rope you grabbed). Given this can you reach your destination?
A1) Key to this puzzle is realising that your best way to get to a rope, is from the rope closest to the beginning which allows you to reach it. So you create an array which is the maximum length of rope for each rope which you are able to use. First rope is easy, since you start off holding it. It sweeps out a section ahead of it and you can fill in the maximum lengths for those. Then repeat for the next rope and the next rope – until you either find a rope which you can’t reach, or are able to reach the destination. By starting your search for the sweep from immediately after the last location filled in (which are all guaranteed to already be right due to the above explanation) and exiting as soon as you exceed the maximum length, you ensure that the running time is O(N), which is kind of important if you have a slow programming language as the large input has a maximum number of ropes of 10000 and the simplest approach can be O(N^2).
Q2) Given a list of circles of specified radii, determine how to place their centres in a provided rectangle such that they do not overlap. The rectangle area is guaranteed to be at least 5 times the sum of the areas of the circles.
A2) With the large input being up to 1000 circles, and the circles being fairly large variability in radius, it seemed likely that some kind of brute force filling was probably going to be too slow. In hindsight, I am not sure this is actually true. O(N^2) with 1000 is trivial enough you could probably just place them in a row across the top long edge, and then try and fill new rows in, shifting towards the top long edge as far as possible based off an exhaustive test of the existing placed circles. I don’t see any reason why this would have troubles with space given that there is about 4 times the space you need. But I’ll include what I did for completeness.
First sort the circles from largest to smallest (something which would probably be important above anyway). Then start rows just like as described before, but rather than trying to push them upwards, try to fill the rows height by stacking circles above one another within the row, if the circles are small enough. This keeps the rows self contained and stops you from having to consider any circles other than the last one you placed in the current and last ‘column’. This gives O(N) for the filling stage, so performance is dominated by the sort. Packing density in this approach is at worst ~pi/8 which is far greater than 1/5. To be safe I special cased long thin scenarios by just lining all the circles in a row, but I think my implementation actually handled them just fine.
I got 2 penalties on this problem, 1 because of some mistakes in my coding, but the other 1 was because the outputs had to be in the same order as the input, and I had forgotten that I had sorted the inputs…
Q3)There are a series of hills each exactly 1km apart. From the peak of each hill, looking out towards the next hill (from ‘left’ to ‘right’), one of the hills has the greatest angle relative to straight down. This hill ‘appears’ to be the highest, even though it may not actually be the highest. Given for each hill which following hill appears to be the highest, determine a set of integer heights between 0 and 1 billion which satisfy these criterion.
A3) The large input had up to 2000 hills which I determined was going to be problematic. My approach was to work from right to left, determine the height range for each hill which caused it to satisfy the criterion and choose any point in that range. The trick being that the range is not guaranteed to contain integers, or be positive. The later is easily fixed, just shift every mountain upwards. The former is of concern. I figured that worst case the range might involve fractions where the basis was of the order of n! where is was the number of hills. Which for n=10 was plausible, so I could just multiply the fractions up by their basis top make them all integers. With a maximum of 1billion, that would be fine. (And in fact the test cases I received only needed up to about 100k). For 2000 hills this is very unlikely to work. Finding the smallest fraction base in a range might have made it feasible, but I don’t know how to do that quickly.
My solution failed because solving for the range involves finding the minimum height such that the current point, its highest and a point behind that are co-linear. And the maximum height for current point, its highest and a point in between. I wrote out the equation for two lines having same slope, which with a common point means co-linear. I then solved for the height, but somehow forgot that the height was in both sides. At runtime this showed up as a divide by 0 error, because my height fraction was uninitialised on the right hand side and internally was equal to 0/0. Kind of confusing trying to debug this with less than 3 minutes left on the clock.
The other bug I had was the minimum and maximum are technically inclusive and exclusive bounds, because the conditions state that in co-linear case you see the front-most. But if you actually use that inclusive bound (and you don’t have to) you can later incorrectly decide that there is no valid option because the middle of that co-linear can no longer be the highest for any future point, but if you didn’t make them co-linear you could point at it directly just fine. I think a few more minutes would have let me solve this one…
The large input… I’ve had a few ideas, the best of which is as follows. Every position which sees a given peak as the highest, can be given equal height. Starting from the right, choose the minimum positive slope which lets all of them see that peak and nothing beyond and gives them an integer value. By construction it should be fairly(?) obvious that this solves the problem as all the problematic cases are where its impossible to solve anyway… The only question is whether the range of heights constructed exceeds the 1billion. I think it can be shown that the worst case has a height difference of O(N^2). Running time is theoretically O(N) if you first group them by which mountain they can see. You also need to first validate the input that it doesn’t make impossible claims, which is that the ranges which claim a two different peaks as highest are mixed, not adjacent or fully contained.
Q4) Given a rectangular grid of squares, some of which are ‘caves’, others are walls and others are just empty, determine two things. Firstly which (how many) empty locations can reach each cave given down/left/right movement (no up) and secondly, does there exist a sequence of moves which moves every element which can reach the cave, to the cave.
A4) I am certainly glad that I choose to work on Q3, because even the small input of a 10×10 grid (which is 8×8 in practice because the outside edges are always walls) has solutions which are ~32 steps in length, and there are 3 possibilities at each step, and all of them can be possible. So a pure brute force is something like O(n^2*3^(n^2/2)) which is insane.
I thought about this for quite a bit after the competition, and didn’t come up with anything which I was confident of. So I consulted the contest analysis. Key points are there is no need to back-track, you just need to ensure you don’t move in an invalid way. (Which gives a randomized solution, you randomly choose between valid moves until you win, but it could take a while…) If you can move down, and there is something to move down, you might as well move down. Moving left/right never take you outside the valid states, so you can move all left/all right to consolidate each row into a single value. Then it just becomes a matter of moving those rows to some point where you can move down.
So, to recap. First move everything full left, if you can move down usefully, then move down. Otherwise step right and try again. Keep trying until you hit a right wall on one row, then sweep left, remembering where you were, then go back to where you were and go right, and sweep left again, until you get to full right and a final sweep left. This covers all the possible scenarios. If you manage to go down, go back to the beginning until you win or fail to find progress. What is the running time of this? I think it is O(N^5) which should be fine for the large input which is N=30.