So, 500th place was the same score as me, just 30minutes faster.\u00a0 If I had of started with question 3 rather than wasting almost an hour on question 1, I would have gotten through.\u00a0 Had I submitted anything else successfully I would have gotten through.<\/p>\n
Exactly 2 Australian’s got through, in 498th and 500th respectively.\u00a0 I was the third highest Australian, and given how I was doing in the first round, 615th was a fairly successful result, just disappointed I don’t get a t-shirt.<\/p>\n
On to the questions…<\/p>\n
Q1) Give a set of numbers laid out in a diamond shape (for instance 1 number on the first row, 2 on the second, 1 on the third), determine the smallest diamond shape of numbers which contains the given diamond, and is horizontally and vertically symmetric.<\/p>\n
A1) This question had a bit of controversy, up until about the 50minute mark (which was when I switched to Q3) the question text was actually incorrect.\u00a0 I would claim this as why I failed to solve the problem, but almost certainly the real reason is because of the midnight start, my approaching head cold and general momentary stupidity :P.<\/p>\n
Possibly the biggest pain with this question is the diamond shape.\u00a0 It is not a nice layout of numbers to work with.\u00a0 I spent a few minutes trying to get my brain cells to work to write code for detecting mirror symmetry in a subset of the diamond before I gave up and rotated the diamond 45degrees, making it a square.\u00a0 Even writing the code to do that wasted about 15minutes, which indicates how well my brain was working.\u00a0 Working with a square with diagonal symmetry checking was much easier, although I still had a bunch of off by one errors I had to fix.\u00a0 In the end I did get that working, but while my answer solved the sample, it did not solve the small…<\/p>\n
As I realised after the competition it was because I was completely screwing up my solution.\u00a0 I was determining 2 mirror symmetries in a subset and mysteriously assuming that could be used as the seed of the smallest double symmetric diamond which contains the original.\u00a0 I was at least having the requirement that the subset included one of the corners, but this approach is just wrong.\u00a0 In the end I have all the code I need to solve the problem, just the wrong algorithm!<\/p>\n
I believe the correct solution is to find the largest single mirror symmetric (along the axis which doesn’t pass through the corner) subset for each corner.\u00a0 Then find the largest sum of pair of non-opposite corners.\u00a0 These 2 will be the seeds of the large diamond.\u00a0 Final answer is 3*original diamond size – sum of sizes of pair of non-opposite corners half symmetric subsets. (Give or take some off-by ones which I may have missed…)\u00a0 All in all given how few points this question was worth, I really should have listened to my first instinct and just ignored it completely.<\/p>\n
Final results for the competition are not announced yet, leaving a tiny hope that I might get through due to the controversy with this problem, but it would be a cheap win which I don’t deserve.<\/p>\n
Q2) Given 2^p teams competing in a knock-out competition, with each match\u00a0 in the knock-out tree having a specific cost and a list of the maximum number of games for each team you are willing to miss, determine the minimum cost to attend the required number of games worst case. (p is up to 10)<\/p>\n
A2) Having up to 1024 teams scared me away from this question quick smart, but it was the one that most people actually solved.\u00a0 The small data set every cost was 1 dollar, the large, the costs varied between 0 and 100000.\u00a0 Even so overflow was not going to be an issue.\u00a0 Even now I can’t immediately see how to solve this, but I am beginning to think that it involves a divide and conquer approach…\u00a0 And pretty much as soon as I’ve thought about the question properly for a minute I have solved it.\u00a0 Define the recursion to be over the minimum cost to satisfy all leaf restrictions of a given branch, having already bought n matches at some parents.\u00a0 Then for each node in the tree, the result is equal to the minimum of the cost of this node and the sums of each child for having bought n+1 matches, and the sum of each child for having bought n matches.\u00a0\u00a0 Terminating condition of infinite cost if we fail to satisfy the maximum games missed for a given team.\u00a0 Finally the result is the grand final match node with having bought 0 already.\u00a0 This can be done using dynamic programming, with an array p by (2^p)-1 using the \/2 to find the parent, *2\/*2+1 to find the children packed tree in array representation.\u00a0 Or you could dynamic program over an actual binary tree, with each node containing an array… performing a depth first walk.\u00a0 Or you could do memotized recursion.\u00a0 Whatever, its all easy – and I really should have taken a closer look at this one!<\/p>\n
Q3) Given an ‘infinite’ grid with cells which are filled in or not, where each cell which has a north or west neighbour stays alive and which has both a north\u00a0 and west neighbour, but is empty, comes alive (simultaneously – so a north east pointing diagonal line of cells slow moves and shrinks to the south east).\u00a0 And up to 1000 large possibly overlapping rectangles which are initially filled in, determine how long before there are no cells filled in.<\/p>\n
A3) I managed to solve this as almost O(N^2) in the number of rectangles.\u00a0 I suspect with the appropriate data structure checking every pair for ‘overlap’ could be reduced to O(N log N) but O(N^2) is plenty for this questions large constraints. (The almost in the first sentence is the O(alpha(n)) amortised cost for each disjoint set tracker union operation.)<\/p>\n
First we divide the problem in to sub-problems.\u00a0 If two sets rectangles are well separated, they do not influence each other in any way.\u00a0 So first of all what counts as separated?\u00a0 If 2 rectangles overlap, then presto that is a guaranteed interaction.\u00a0 If they don’t come close to touching at all (separated by at least one in any axis), they are separate.\u00a0 If they are horizontally or vertically immediately adjacent, they act together.\u00a0 This leaves diagonally adjacent.\u00a0 Corners touching in the north east\/south west directions count, but the north west\/south east directions do not.\u00a0 I used a disjoint set tracker (I love this thing!) to track which act together and which do not.\u00a0 This part of the problem actually turns out to be the most expensive, since the rest runs in O(N).<\/p>\n
Once they are separated we can treat each section individually and take the maximum of each problem.\u00a0 So given n rectangles which interact, how long do they last?\u00a0 It is fairly easily apparent that no matter how the north west corners get trimmed at each time step, the south east growth areas grow first.\u00a0 So the last cell to go will be the south east most part that either grows or is already there.\u00a0 Growth areas are limited by the south most edge and east most edge of all constituent rectangles.\u00a0 The tricky bit is determining which of the first cells to go will be the start of the cascade which reaches that final location.\u00a0 Although actually when it is phrased like that, it becomes somewhat obvious.\u00a0 Since the area which dies moves south east, the most north west point is going to be the start of the final cascade, all other locations will get stuck against one of the walls belonging to that location.\u00a0 That may sound convincing but proving it is probably more complicated.\u00a0 I managed to convince myself well and truly before I wrote my solution, but my reasoning is not a proper proof, although I am sure one exists.\u00a0 So comparing the north west corners to select the one which lies on the most north-west diagonal, and taking the maximum of the south east corners, we have the ‘effective rectangle’ for the group of rectangles which interact.\u00a0 A single rectangle takes height + width – 1 turns to disappear, and this also works with the effective rectangle.\u00a0 So we finally return the maximum of each disjoint set, and we’re done.\u00a0 Only 60 people got this out, so I was quite happy.<\/p>\n
Q4) Given N points which each have a goat tied to it, and M possible locations for a bucket which each goat must be able to reach, determine for each bucket the minimum area which all goats can reach, by adjusting the goat ropes to whatever length you like.<\/p>\n
A4) I spent my last 25minutes doing the small problem set for this.\u00a0 If I had of successfully submitted it, I was through, and I realised that at the time, so the pressure was on.\u00a0 The small problem set limited N to 2, which is the easiest case of the overlapping circles problem.\u00a0 When I saw this I thought, cool that will be simple I’ll just jump on mathworld copy the formula into my code and submit it… Which I did.\u00a0 And it failed.\u00a0 Oh I have a bug.\u00a0 Fix that, still fails.\u00a0 Oh what about this special case, fix that (later realise that the problem explicitly excluded it from being possible), still fails.\u00a0 Hmm maybe numeric accuracy in the acos function parameters, avoid unneeded square roots… still fails.<\/p>\n
What can I say it was 2am, I couldn’t quite activate enough brain cells to realise that the formula from mathworld was wrong…\u00a0 Well not exactly wrong, more, insufficiently correct.\u00a0 The mathworld solution only handled the case where the circle intersection points form a line which crosses the segment joining the circle centres.\u00a0 If the resultant area is made up of 2 circle subsections where one of the circle subsections is more than half of a circle, it produces the wrong result.\u00a0 In that case the area is the sector + the triangle, rather than the sector – the triangle.\u00a0 If I had of actually sat down and derived the formula I might have gotten this correct, but 25minutes at 2am, it wasn’t going to happen.<\/p>\n
The large problem set, N is up to 5000, M is up to 1000.\u00a0 Even if I had the formula for the area of a truncated circle and an arbitrary convex polygon already written (which is something I should really get around to doing for TMD.Algo), I suspect I would take a long time to write the solution, and even then I think it would be O(N^2 * M) at best, which is very risky timewise.\u00a0 I think something like the convex hull algorithm must come in to play.\u00a0 Only 2 people got this problem out and they came 7th and 27th.\u00a0\u00a0 The top 6 got everything out except for this.<\/p>\n
I actually think I have seen this question asked in topcoder before, so its probably worth being added to TMD.Algo in its entirety.<\/p>\n
So that is most likely it for GCJ10 for me this year, I’ll write up the analysis for R3, which will likely contain some interesting questions – they save the best for last…\u00a0 Next stop is round 1 of TCO10.<\/p>\n","protected":false},"excerpt":{"rendered":"
So, 500th place was the same score as me, just 30minutes faster.\u00a0 If I had of started with question 3 rather than wasting almost an hour on question 1, I would have gotten through.\u00a0 Had I submitted anything else successfully I would have gotten through. Exactly 2 Australian’s got through, in 498th and 500th respectively.\u00a0 … Continue reading GCJ10 R2 Analysis<\/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,6],"tags":[],"class_list":["post-175","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/175","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=175"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/175\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=175"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=175"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=175"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}