So, 500th place was the same score as me, just 30minutes faster. If I had of started with question 3 rather than wasting almost an hour on question 1, I would have gotten through. Had I submitted anything else successfully I would have gotten through.
Exactly 2 Australian’s got through, in 498th and 500th respectively. 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.
On to the questions…
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.
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. 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.
Possibly the biggest pain with this question is the diamond shape. It is not a nice layout of numbers to work with. 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. Even writing the code to do that wasted about 15minutes, which indicates how well my brain was working. 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. In the end I did get that working, but while my answer solved the sample, it did not solve the small…
As I realised after the competition it was because I was completely screwing up my solution. 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. I was at least having the requirement that the subset included one of the corners, but this approach is just wrong. In the end I have all the code I need to solve the problem, just the wrong algorithm!
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. Then find the largest sum of pair of non-opposite corners. These 2 will be the seeds of the large diamond. 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…) 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.
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.
Q2) Given 2^p teams competing in a knock-out competition, with each match 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)
A2) Having up to 1024 teams scared me away from this question quick smart, but it was the one that most people actually solved. The small data set every cost was 1 dollar, the large, the costs varied between 0 and 100000. Even so overflow was not going to be an issue. 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… And pretty much as soon as I’ve thought about the question properly for a minute I have solved it. 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. 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. Terminating condition of infinite cost if we fail to satisfy the maximum games missed for a given team. Finally the result is the grand final match node with having bought 0 already. 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. Or you could dynamic program over an actual binary tree, with each node containing an array… performing a depth first walk. Or you could do memotized recursion. Whatever, its all easy – and I really should have taken a closer look at this one!
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 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). And up to 1000 large possibly overlapping rectangles which are initially filled in, determine how long before there are no cells filled in.
A3) I managed to solve this as almost O(N^2) in the number of rectangles. 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.)
First we divide the problem in to sub-problems. If two sets rectangles are well separated, they do not influence each other in any way. So first of all what counts as separated? If 2 rectangles overlap, then presto that is a guaranteed interaction. If they don’t come close to touching at all (separated by at least one in any axis), they are separate. If they are horizontally or vertically immediately adjacent, they act together. This leaves diagonally adjacent. Corners touching in the north east/south west directions count, but the north west/south east directions do not. I used a disjoint set tracker (I love this thing!) to track which act together and which do not. This part of the problem actually turns out to be the most expensive, since the rest runs in O(N).
Once they are separated we can treat each section individually and take the maximum of each problem. So given n rectangles which interact, how long do they last? 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. So the last cell to go will be the south east most part that either grows or is already there. Growth areas are limited by the south most edge and east most edge of all constituent rectangles. The tricky bit is determining which of the first cells to go will be the start of the cascade which reaches that final location. Although actually when it is phrased like that, it becomes somewhat obvious. 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. That may sound convincing but proving it is probably more complicated. 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. 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. A single rectangle takes height + width – 1 turns to disappear, and this also works with the effective rectangle. So we finally return the maximum of each disjoint set, and we’re done. Only 60 people got this out, so I was quite happy.
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.
A4) I spent my last 25minutes doing the small problem set for this. If I had of successfully submitted it, I was through, and I realised that at the time, so the pressure was on. The small problem set limited N to 2, which is the easiest case of the overlapping circles problem. 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. And it failed. Oh I have a bug. Fix that, still fails. Oh what about this special case, fix that (later realise that the problem explicitly excluded it from being possible), still fails. Hmm maybe numeric accuracy in the acos function parameters, avoid unneeded square roots… still fails.
What can I say it was 2am, I couldn’t quite activate enough brain cells to realise that the formula from mathworld was wrong… Well not exactly wrong, more, insufficiently correct. The mathworld solution only handled the case where the circle intersection points form a line which crosses the segment joining the circle centres. 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. In that case the area is the sector + the triangle, rather than the sector – the triangle. 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.
The large problem set, N is up to 5000, M is up to 1000. 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. I think something like the convex hull algorithm must come in to play. Only 2 people got this problem out and they came 7th and 27th. The top 6 got everything out except for this.
I actually think I have seen this question asked in topcoder before, so its probably worth being added to TMD.Algo in its entirety.
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… Next stop is round 1 of TCO10.