With 2000 qualifiers able to sign up, only 1550 actually did.<\/p>\n
I started writing this post while the solutions were going up, I wasn’t very impressed with my effort (even allowing for the 2am start time and the remnants of the head-cold I’ve had over the last few days), and fully expected that I had failed to make it through to the next round.\u00a0 Scores were still updating but I was 852 and very few re-orderings were occurring due to system test failures.\u00a0 However, at that point I also thought that the cut-off was the top 600.\u00a0 I was wrong – top 850 go through – and final results have me at 845th!<\/p>\n
I guess that means I get the privilege of waking up at 2am next week, along with the 6 other Australian’s who progressed. Only 8 Australians bothered to wake up (including myself), I’m sure more qualified than that…<\/p>\n
Q1) Given a sequence of characters X and O, you want to reorder them into a different sequence.\u00a0 4 operations are available, move the front to the end of either of 2\u00a0 separate storage locations, or move the front of either of the 2 separate storage locations to the end of the original.\u00a0 Return the minimum number of operations required.<\/strong><\/p>\n A1) Simple! – although at 2am nursing a muddled head it certainly took me long enough – a few seconds longer and I would have been eliminated this round.\u00a0 The answer is 2 times the minimum number of characters to remove from the front before the rest is equal to the start of the desired sequence.<\/p>\n Obviously there is no way it can be smaller than this, all that remains is to justify that it can always be achieved in this number of turns.\u00a0 To do this, all it takes is to realize that there are 2 storage locations and 2 character types.\u00a0 So every X you move to storage 1 and every 0 you move to storage 2.\u00a0 Then you can put them back on to the end of the initial location in whatever order you like, no restrictions since each storage is all the same character.<\/p>\n Q2) Given a set of probabilities that a road segment is muddy, and the ability to jump over any single road segment you like, what is the expectation value for the minimum number of muddy road segments you have to stand in to get from start to end? (Start and end are both guaranteed to be dry.)<\/strong><\/p>\n A2) As probability problems go, this one isn’t as bad as some.\u00a0 However, my first write up I tried to build from start to finish, rather than from finish back to start – which was completely wrong, so I had to scrap that and start again.\u00a0 I then made about a dozen mistakes getting 0 and 1 mixed up.\u00a0 No idea why but I had decided to choose 1 as dry and 0 as muddy and half way through I switched that all backwards…\u00a0 I should have realised that 0 as dry and 1 as muddy was a more natural assignment from the start.\u00a0 I finally sorted them all out, but only a couple of minutes after the end of the available coding time!<\/p>\n So I wrote the solution as a recursion of expectation value for a given position depending on whether the position closer to the finish is muddy or not as well as the current position is muddy or not. (Apparently it can even be defined as a straight recursion, like a complicated version of the Fibonacci series – but I am too tired to see the path to that.)\u00a0 From there the answer is the sum of the two scenarios for position 0(start) where they are not muddy, weighted average by the probability of each scenario which is given by the probability of position 1 being muddy.\u00a0 Memotized recursion or DP to the answer.<\/p>\n Details of the recursion are rather long to fully write out, but can be summarized as a couple of conditions. If the next position is dry, take expectation value of that position for the dry case (2 scenarios weighted average), and then add 1 if the current position is muddy.\u00a0 If the next position is wet, take expectation value of the position after in either dry or wet case (4 scenarios weighted average) and add 1 if the current position is muddy.<\/p>\n This works because if the next cell is dry jumping is not required, and worst case you jump into mud, so you never try jumping.\u00a0 If next cell is muddy, you always jump, because if the cell after is dry its a winner, if it is muddy then you have stepped in the same number of muddy cells as if you had not jumped, but you are closer to the finish (that is not a formal proof, but hopefully obvious).<\/p>\n Q3) Imagine IP addresses where each of the 4 components are valued 0 to 999.\u00a0 Then imagine that you effectively own all of them, and that people are willing to pay for each IP address.\u00a0 Up to 50 people make a request for 1 or more IP addresses and give a price they are willing to pay per address.\u00a0 Each request is in the dotted form, with wild cards allowed for any\/all of the 4 segments(no partial wild cards, each segment is either a number or a match anything wild card).\u00a0 Determine the maximum profit to be made.<\/strong><\/p>\n A3) Interesting question.\u00a0 With up to 50 trillion operations in brute force, there definitely needs to be some accelerated counting.<\/p>\n One failed solution I saw calculated all intersections, to gather each section where there is multiple possibilities. Sort them by size largest to smallest, then do inclusion\/exclusion counting to get the answer.\u00a0 I think the general principle was sound, but the implementation was lacking.\u00a0 The trick comes in determining inclusion\/exclusion counting.\u00a0 Worst case for unique intersections is less than 70000, but for each one it could be the result of many different ways of combining, some of which might be needing an inclusion, while others need an exclusion (I think?).\u00a0 I am thinking forming them into a potentially interlinking forest, which is depth first searched from each root with some kind of memotization to produce the result without a performance explosion.<\/p>\n 5am has arrived, I’ll have to come back to this one. (And maybe QR3, which I never wrote up…)<\/p>\n","protected":false},"excerpt":{"rendered":" With 2000 qualifiers able to sign up, only 1550 actually did. I started writing this post while the solutions were going up, I wasn’t very impressed with my effort (even allowing for the 2am start time and the remnants of the head-cold I’ve had over the last few days), and fully expected that I had … Continue reading TCO11 R1<\/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-409","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\/409","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=409"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/409\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}