So this one was at a more reasonable time, so I participated.\u00a0 281st, not as good as I might like, but good enough to get through.<\/p>\n
Q1) Given a scrambled list of two item types with a total count of N, and the ability to at most once for each i in 1 to N switch two elements that far apart, determine the minimum number of swaps to order the list, if it is possible.<\/strong><\/p>\n A1) So, the answer to this question was so obvious that it takes a while to see.\u00a0 In the case of there only being 2 element types a single pivot sort pass will result in an ordered list.\u00a0 If you consider a pivot sort where you walk from the outside towards the middle, swapping if both are on the wrong side, walking a specific end if it is on the right side – you can see that it will perform a minimal number of swaps and that every swap will be closer than the last.<\/p>\n Hence it is always possible to sort, and the answer is just the count of the number of items not in the right spot to start with\/2.\u00a0 Or you can simulate the pivot sort, like I did.<\/p>\n Q2) Given a ‘map’ (1 dimensional array) which shows the position of two critter types, which are either grumpy at time t % K = 0 or at t % C != 0, determine the minimum time to get from the left to the right of the map if you cannot by in a cell at a time when its occupant is grumpy, if it is even possible.\u00a0 Maximum value for K,C and length of array are all 50.<\/strong><\/p>\n A2) So this is really pretty easy, its a shortest path algorithm, with a small twist.\u00a0 Because the behaviour of a critter depends on time, each cell needs to be replicated in the graph to represent how time plays a part.\u00a0 Obviously replicating once for every time step defeats the whole purpose of a shortest path algorithm… but since behaviours are dependent on mod K and mod C, it is pretty obvious that t mod K and t mod C are the only things that matter for a given cells possible future paths.\u00a0 So each cell is replicated K*C times (or LCM(K,C) if you want to get really fancy, but given the availability of primes near 50, worst case for K*C and LCM(K*C) are pretty close…<\/p>\n So 50*50*50 vertexes in the graph, and 3 edges from each vertex.\u00a0 From there you just use a priority queue based Dijkstra algorithm and presto, successful solution done.<\/p>\n I on the other hand used a non-priority queue – which for a while I had convinced myself should perform much slower in the worst case.\u00a0 Shows how rusty I am!\u00a0 graphs with equal edge distances don’t need a priority queue as a normal queue already walks them in breadth first search order.\u00a0 Using a priority queue would only make things slower by adding the logarithmic insert\/remove cost overhead.\u00a0 So yeah, in hindsight my algorithm works pretty well…\u00a0 If .Net had of had a built in priority queue I probably would have used it and only made things marginally worse!<\/p>\n Q3) Define S(x) to be the sum of the digits in x.\u00a0 Define D(x) to be the recursive application of S until the input equals the output.\u00a0 Given a range, determine how many of the contained numbers can be represented as y*D(y).\u00a0 Range constraints: less than 10 billion.<\/strong><\/p>\n A3) This problem was easy! – unfortunately I only realized as much with 10minutes on the clock, and I just wasn’t fast enough to write it all up.\u00a0 I was 4 lines of code from being complete. (Although said 4 lines require a little bit of thought each…)\u00a0 If I had of rushed rather than taking everything at an easy pace I might have saved those extra 2-3 minutes I needed to finish those 4 lines and perform the final debugging.\u00a0 That would have gotten me in the top 40, which is where I know I am capable of reaching.<\/p>\n D(y) = 9 if y is a multiple of 9 else y mod 9.\u00a0 If you’ve played around with digit sums before you would know this, if not a short exploration should make it fairly obvious.\u00a0 So y*D(y) can be decomposed into 9 linear functions, which sometimes overlap.\u00a0 Includes\/Exclusion principle applies, so you can sum, subtract, sum, subtract your way through every possible n choose 9.\u00a0 That is quite a few equations to write out, but everyone of them is pretty simple – if you could be bothered…<\/p>\n However! Every one of the 9 equations is of the form a*9k+b.\u00a0 Note that these equations all have constant ‘mod 9’ values and they aren’t all the same.\u00a0 Hence many pairs don’t have any overlap and so the inclusion\/exclusion can be simplified significantly.\u00a0 It decomposes into 3 pairs and 1 triple. This means you only need 9 base equations, 5 pair equations, and 1 triple equation.\u00a0 I was half way through the pair equations when time ran out.\u00a0 Interestingly I found one of the pair equations cancels with one of the base equations, and apparently there are more cancellations because looking at once of the successful answers, they only needed 9 equations and 7 of those were base equations. (So technically I was 2 lines of code away from being finished :P, 1 add and 1 delete…)<\/p>\n","protected":false},"excerpt":{"rendered":" So this one was at a more reasonable time, so I participated.\u00a0 281st, not as good as I might like, but good enough to get through. Q1) Given a scrambled list of two item types with a total count of N, and the ability to at most once for each i in 1 to N … Continue reading TCO11 QR2<\/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-330","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\/330","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=330"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/330\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=330"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=330"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}