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.\u00a0 Far from ideal conditions and maybe they contributed to my just missing out on making it through to round 3.\u00a0 9th placed Australian, in 543rd place.\u00a0 Tikitiki and Aussie got great starts this round, I think they must have seen some of these kinds of questions recently or something…<\/p>\n
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.\u00a0 So my first problem submission time was not great.\u00a0 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.\u00a0 But it only left me 30minutes to try to get one more small input.\u00a0 I figured I needed to go for Q3 to be safe as it seemed easier and was worth more points.\u00a0 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.\u00a0 I realised the problem at 1minute left, but wasn’t fast enough to fix it.\u00a0 (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.\u00a0 Getting it right would have been a top 250 placing, which would have been great.)<\/p>\n
In any case I have a nice new t-shirt, which was the only prize I was going to get… in this competition anyway…<\/p>\n
Q1) There are ropes hanging down from points.\u00a0 Each rope has a given length and given position.\u00a0 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.\u00a0 You start off holding the first rope.\u00a0 You can swing out and grab any rope in your path.\u00a0 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).\u00a0 Given this can you reach your destination?<\/strong><\/p>\n 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.\u00a0 So you create an array which is the maximum length of rope for each rope which you are able to use.\u00a0 First rope is easy, since you start off holding it.\u00a0 It sweeps out a section ahead of it and you can fill in the maximum lengths for those.\u00a0 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.\u00a0 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).<\/p>\n 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.\u00a0 The rectangle area is guaranteed to be at least 5 times the sum of the areas of the circles.<\/strong><\/p>\n 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.\u00a0 In hindsight, I am not sure this is actually true.\u00a0 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.\u00a0 I don’t see any reason why this would have troubles with space given that there is about 4 times the space you need.\u00a0 But I’ll include what I did for completeness.<\/p>\n First sort the circles from largest to smallest (something which would probably be important above anyway).\u00a0 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.\u00a0 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’.\u00a0 This gives O(N) for the filling stage, so performance is dominated by the sort.\u00a0 Packing density in this approach is at worst ~pi\/8 which is far greater than 1\/5.\u00a0 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.<\/p>\n 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…<\/p>\n Q3)There are a series of hills each exactly 1km apart.\u00a0 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.\u00a0 This hill ‘appears’ to be the highest, even though it may not actually be the highest.\u00a0 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.<\/strong><\/p>\n A3)\u00a0 The large input had up to 2000 hills which I determined was going to be problematic.\u00a0 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.\u00a0 The trick being that the range is not guaranteed to contain integers, or be positive.\u00a0 The later is easily fixed, just shift every mountain upwards.\u00a0 The former is of concern.\u00a0 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.\u00a0 Which for n=10 was plausible, so I could just multiply the fractions up by their basis top make them all integers.\u00a0 With a maximum of 1billion, that would be fine.\u00a0 (And in fact the test cases I received only needed up to about 100k).\u00a0 For 2000 hills this is very unlikely to work.\u00a0 Finding the smallest fraction base in a range might have made it feasible, but I don’t know how to do that quickly.<\/p>\n 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.\u00a0 And the maximum height for current point, its highest and a point in between.\u00a0 I wrote out the equation for two lines having same slope, which with a common point means co-linear.\u00a0 I then solved for the height, but somehow forgot that the height was in both sides.\u00a0 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.\u00a0 Kind of confusing trying to debug this with less than 3 minutes left on the clock.<\/p>\n 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.\u00a0 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.\u00a0 I think a few more minutes would have let me solve this one…<\/p>\n The large input…\u00a0 I’ve had a few ideas, the best of which is as follows.\u00a0 Every position which sees a given peak as the highest, can be given equal height.\u00a0 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.\u00a0 By construction it should be fairly(?) obvious that this solves the problem as all the problematic cases are where its impossible to solve anyway…\u00a0 The only question is whether the range of heights constructed exceeds the 1billion.\u00a0 I think it can be shown that the worst case has a height difference of O(N^2).\u00a0 Running time is theoretically O(N) if you first group them by which mountain they can see.\u00a0 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.<\/p>\n Q4) Given a rectangular grid of squares, some of which are ‘caves’, others are walls and others are just empty, determine two things.\u00a0 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.<\/strong><\/p>\n 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.\u00a0 So a pure brute force is something like O(n^2*3^(n^2\/2)) which is insane.<\/p>\n I thought about this for quite a bit after the competition, and didn’t come up with anything which I was confident of.\u00a0 So I consulted the contest analysis.\u00a0 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…)\u00a0 If you can move down, and there is something to move down, you might as well move down.\u00a0 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.\u00a0 Then it just becomes a matter of moving those rows to some point where you can move down.<\/p>\n So, to recap.\u00a0 First move everything full left, if you can move down usefully, then move down.\u00a0 Otherwise step right and try again.\u00a0 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.\u00a0 This covers all the possible scenarios.\u00a0 If you manage to go down, go back to the beginning until you win or fail to find progress.\u00a0 What is the running time of this?\u00a0 I think it is O(N^5) which should be fine for the large input which is N=30.<\/p>\n","protected":false},"excerpt":{"rendered":" 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.\u00a0 Far from ideal conditions and maybe they contributed to my just missing out on making it through to round 3.\u00a0 9th placed Australian, in 543rd place.\u00a0 Tikitiki and … Continue reading GCJ12 R2<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-557","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/557","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=557"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/557\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=557"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=557"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=557"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}