So it appears I am through to round 2, not that that is amazing news or anything.<\/p>\n
Qualifying round was pretty easy, solved all the problems – like 2392 other people.
\n7516 people qualified with a minimum score of 33, over 8000 people submitted at least one correct answer for a small data set. So quite a few people gave it a shot obviously.<\/p>\n
First question could be solved within the constraints by brute force. Although there was potential for optimisations of the average case, I couldn’t see a reliable worst case improvement. And any such optimisations were too complicated to be bothered with anyway.
\nSecond question was a bit more interesting. The constraints of the large input set were enough that the simplest solution would be unlikely to execute quick enough (I think…). I immediately thought of using a disjoint set data structure, but I was too lazy to open up TMD.Algo and copy my code. It would have been a simpler solution but in my laziness I went with a dfs based method which was possible since each disjoint set had a single root node which was easily identifiable. Ultimately the running time for both cases is O(n) where n is the land area w*h. The disjoint set data structure would have had a better constant though. (Since i did not cache which way a given square flowed with my dfs approach each square might be asked its flow direction once for each neighbour.)
\nThird question was a straight forward stock standard dynamic programming (or cached recursion), although the small data set could conceivably be brute forced.<\/p>\n
Round 1A – I had a doh moment just after finishing this one, when I realised that 40 choose 20 is much smaller than long.MaxValue. I spent the last 10 minutes trying to reorganise my code to avoid an overflow, which probably would never have occurred anyway. I probably could have easily gotten another 30 points as a result, taking my 37\/100 to 67. It doesn’t matter though, Solving the small data set for the first problem in less than 45minutes (including time penalties), or solving anything else was sufficient to progress as part of the Round 1A top 1000. My 37 (in 2:20) was sufficient for 403rd place, 67 would have gotten me to about 200th, a much more respectable number given 1A probably was missing a lot of the good European time zone contestants who will likely compete in 1B. 1B is in less than 11 hours now, but I think I’ll avoid staying up late until I have to for round 2. (I could do the problems as an observer and try to to keep to the time limit to practice more realistically, but having just come back from overseas some sleep would be an idea I suspect.)<\/p>\n
To the questions – much harder than qualifying round of course:
\nQuestion 1 – Happy numbers – the small data set for this should have been pretty easy. With a maximum of 3 constraints to be met simultaneously the maximum answer is easily small enough to be brute forced. I was pretty happy with my simple solution though, even with up to 9 constraints as in the large data set (although base 2 is irrelevant since all base 2 numbers greater than 0 are happy) you can brute force the full set of all 256 (ignoring base 2) constraint sets pretty quickly I think the maximum answer was under a hundred million. Then either having saved them to disk (I didn’t bother), or computing them once up front, you can answer all 500 inputs in a moment. (Given there were 500 inputs and 511 different possible inputs, you were pretty much guaranteed to be asked for any given combination, so calculating them all at once was an obvious win).
\nQuestion 2 – I didn’t do this one, but the small data set looked doable by brute force. It was just complicated enough to not bother given the third question and how slow I am. I haven’t looked at any of the successful solutions but I didn’t see any obvious way to do the large data set at the time. Thinking for a moment now I see that the problem really is a shortest path graph problem after all, despite the edge lengths being different depending on when you arrive at a given node, the shortest path can still be determined using the simple repeated reductions method. I’m not 100% sure if convergence is guaranteed to be in O(EV) but it certainly should be close enough if not. (Had a look at a solution now, and if you use a time based priority queue you can do it in approx O(V log V + E). Since there are no negative edges a priority first search is guaranteed to only need to visit each vertex once, you just need to allow potential overhead of the priority queue.)
\nQuestion 3 – Probability questions, oh how I hate them. With an unusually high tolerance of 10^-5 I thought possibly I could get away with randomised trials. It became quickly apparent that convergence was to slow even for the small data set. So I went back to doing it the correct way. Its so rare that I actually have to do real math these days that formulating a few simple relationships took me almost an hour. But eventually I got the right formula for the central part of the recursion and the small data set was solved. The hardest part was working out the correct self-recurrence relation to factor out the infinite recursion case. I already had all the caching I needed to solve the large data set, but an incorrect assumption that choices from 40 items was too large for my 64bit integer code to handle led me way down a garden path of wasted time. I do think I’ve seen almost an identical question before, I can’t remember if it was last years code jam though or somewhere else. (Side note, this problem is as a dynamic programming problem with running time n^2, if it wasn’t for overflow and accuracy the constraints could have been made much higher.)<\/p>\n
One note here, I did discover that the latest copy of TMD.Algo has a typo in the Choose implementation which means it is completely useless. That’s what I get for not having any unit tests on the combinatorics library yet. I guess I should release a new version at some point. I should also add a cached choose function which derives its values using the Pascal’s triangle method, slower for a single calculation but also less risk of overflow.
\nI also think I should write the self recurrence calculation for expectation values, since it is non-obvious.<\/p>\n","protected":false},"excerpt":{"rendered":"
So it appears I am through to round 2, not that that is amazing news or anything. Qualifying round was pretty easy, solved all the problems – like 2392 other people. 7516 people qualified with a minimum score of 33, over 8000 people submitted at least one correct answer for a small data set. So … Continue reading Google Code Jam 09 Early Rounds<\/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-78","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\/78","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=78"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/78\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=78"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=78"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=78"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}