Seems low turn out is normal now – 1214 registered out of a possible 1950.\u00a0 6 Australians braving the 2am start.<\/p>\n
Tough round again, top 50 was determined by having solved the 250 and 500pt, with a couple of 250pt only thrown in through large challenge success rates.\u00a0 Despite throwing away some points with an obviously wrong challenge of a correct solution and getting off to a slow start with multiple silly bugs in my 250pt code, I managed to get top 400 placing and my TC rating went back over 1700 again.\u00a0 But still not in the running to get a t-shirt.<\/p>\n
Q1) Given 3 infinite arithmetic series which you can freely slide to different integer offsets determine the maximum minimum gap between any 2 numbers amongst the 3 series.\u00a0 The 3 infinite series are defined by their spacings a,b,c which are all between 1 and 2000 inclusive.<\/strong><\/p>\n A1) Initial guess was GCD(a,b,c)\/3 rounded down – but that doesn’t work for cases like 20,30,40 (which was one of the given test cases helpfully).<\/p>\n As it turns out, the answer is either min(GCD(a,b)\/2, GCD(b,c)\/2, GCD(a,c)\/2) or GCD(a,b,c)\/3 (both cases, rounding down) – the determining factor being whether all 3 pairwise gcds are equal or not.\u00a0 Equal results in the second case, not equal results in the first case.<\/p>\n But since the problem states that the maximum range is 1 to 2000, you can find the solution with a bit less smarts and a bit more brute force. (As I did.)\u00a0 Firstly you observe that offset of one of the arrays doesn’t matter, it can be fixed at offset 0 – since it is an infinite scenario, the origin is meaningless.\u00a0 Secondly, it is obvious that an offset greater than the sequences spacing adds no value, since again the sequences are infinite.<\/p>\n This leaves 4 million scenarios to evaluate.\u00a0 So long as we can do so quickly, we are done.\u00a0 So for a pair of infinite sequences (with spacings s1 and s2) with a relative offset of i – what is the closest approach?\u00a0 Turns out this isn’t too difficult to work out – it is min (i % gcd(s1, s2), gcd – (i % gcd(s1, s2)).\u00a0 So calculate this for all 3 pairs and take the minimum then return maximum of those across all scenarios.\u00a0 My implementation (mostly pointlessly) went a bit faster than this by skipping the inner loop if the outer loop gave a pair of sequences which was worse than the current best.\u00a0 Also the outer loop can be simplified to between 0 and gcd(a,b) rather than 0 and b.\u00a0 However a mistake I made at first was trying to make the same range reduction for the inner loop – which isn’t valid as it doesn’t fully explore the combinations of modulus.<\/p>\n Q2) Given a directed graph of up to 50 vertices, where edges can come in 3 different flavours (and any given pair of vertexes can therefore have up to 3 edges in each direction between them) a game is played.\u00a0 This game involves one person choosing a starting location and announcing the flavour of each transition made to move to a new location.\u00a0 The second person then tries to state with certainty where the first person currently is.\u00a0 If the first person reaches a dead-end, they must declare as such, and the game is over (even if there are multiple dead-ends).\u00a0 Game is scored by the number of moves the first player makes before the game is over.\u00a0 Given the graph, and assuming optimal play by player 1, return how long the game is – or -1 if the game is infinitely long.<\/strong><\/p>\n A2)\u00a0 So it isn’t too hard to write a solution to this problem (which I did) – it is however much more difficult to write one which isn’t too slow in some corner cases.\u00a0 I actually tried to construct a large test case to break my solution, and failed – but the system tester did not.\u00a0 My solution approached the problem from player 2’s perspective.\u00a0 At the start the ‘possible space’ is the set of all locations.\u00a0 Each called out transition maps the possible space to a new possible space.\u00a0 If that space consists of a single location – the game is over.\u00a0 If that space is empty, the optimally playing player could not have called that transition out.\u00a0 A simple dictionary approach lets you store how many moves remain for a given state.\u00a0 When you first see a state you store -1 – thus if you see a state on your current path you can immediately return -1, but if not you can replace that -1 with the actual best number of turns possible.\u00a0 Running cost of this is worst case O(n^2*2^n) – which for n=50 is way too slow. (Using bitwise operations like I did its O(n*2^n) 64bit integer operations, but that is only valid till n=64, and its not a significant improvement anyway.)\u00a0 But constructing this worst case is non-trivial – so I gave it a shot (and failed).<\/p>\n It appear the correct approach is to consider that for player 2 it doesn’t matter whether there are 2 or 22 possible locations, anything greater than one rules out the game ending.\u00a0 So if you take any pair of locations, and consider the possible ways to map that pair to another pair and so on and so on – if you ever find the same pair again, you’ve created a loop and the game can continue forever, but if your search always terminates (no mapping for pair, or only mapping is to them both going to the same node) it isn’t too far of a stretch to see that the best number of turns you find in this search (starting from each possible starting pair) is the same as the best number of turns from the more extensive search.<\/p>\n Q3) Given an initially empty rectangle of size x, y – and the ability to perform 2 operations where you select a sub-rectangle sx, sy and fill 0 or more of the squares in the sub-rectangle – determine how many possible different final states there (modulo large prime) x and y bounded to at most 40.<\/strong><\/p>\n A3) Only 2 solvers for this problem.\u00a0 Answers look like serious combinatorics – adding and subtracting numerous cases.\u00a0 Seems to break it down into rectangle size where changes are made.\u00a0 For each rectangle size where changes are made count how many possibilities, and multiply that by number of possible offset locations of that rectangle in the larger rectangle.\u00a0 That somehow makes the counting of possibilities a bit easier.\u00a0 Seems that for each of these rectangles you consider the case where the 2 sub-rectangles are fixed to opposite corners – and then subtract off the overlap between the 2 cases of opposite corner.\u00a0 Then there is some magic to do with the edges of the rectangles which must be to avoid some kind of double-counting – its all way too complicated for me at 5am in the morning…<\/p>\n","protected":false},"excerpt":{"rendered":" Seems low turn out is normal now – 1214 registered out of a possible 1950.\u00a0 6 Australians braving the 2am start. Tough round again, top 50 was determined by having solved the 250 and 500pt, with a couple of 250pt only thrown in through large challenge success rates.\u00a0 Despite throwing away some points with an … Continue reading TCO13 R2B<\/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-665","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\/665","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=665"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/665\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=665"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=665"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=665"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}