So pre challenge phase I was on 531st – with the feeling that things could go either way for me – the 500pt had the opportunity for lots of failures because of floating point error margins, which I was confident I had taken care of – but on the other hand, a small missed optimisation I noticed with 15seconds to go, left me uncertain whether it was possible to write a degenerative test case which would cause a time-out.<\/p>\n
After challenge I was 480th, with a bit more confidence having seen someone successfully challenge 2 others but not my solution, using what I am pretty sure would have been a time-out attempt.<\/p>\n
My solution to the 500pt did fail system tests, but in-spite of that my final placing was 471st.\u00a0 There were a very large number of failures for the 500pt problem.\u00a0 In my case it was a degenerative performance test case, as I expected.<\/p>\n
471st gets me through to round 2, no need to slog through R1B and\/or R1C.\u00a0 R2A\/B\/C happen after daylight savings change, so I think they will be at 2am instead of 4am.\u00a0 I am not sure which is worse really…<\/p>\n
The 250pt question was easy, and really so was the 500pt – but it took me over half an hour to realise the obvious aspect of the 500pt problem I was missing.\u00a0 I blame having to code at 4:30am…\u00a0 The 1000pt was not – but still there was ~80 submissions for it.<\/p>\n
Q1) Given a set of numbers in the range 0-9, what is the minimum cost (where it costs 1 per integer distance a number is moved by) to ensure all the numbers are within 1 of each other.<\/strong><\/p>\n A1) The limited range made brute force trivial – just try pair of adjacent numbers (0,1), (1,2) … (8,9) and calculate the cost to move each number below to the bottom number and each number above to the higher number.\u00a0 I managed to score 240 out of 250 points here, which is pretty high for me – but it was a pretty easy problem…\u00a0 Competition advancement cut-off was 234 points – so I didn’t want to be too much slower though!<\/p>\n Q2) Given a set of ‘gaps’ which start and end on integer boundaries (but are exclusive of the boundaries themselves) determine the smallest number where all multiples of that number do not fall into any of these gaps.<\/strong><\/p>\n A2) I saw several solutions to this, and many of them failed.\u00a0 Most of them used floating point numbers for doing most of their code, which was a big risk due to cumulative errors.\u00a0 Others failed (like mine) because the code didn’t scale well enough.<\/p>\n The key point which took me far too long to realise was that any candidate solution can be improved so long as none of the multiples lie on the end point of a gap.\u00a0 Otherwise a microscopic reduction in jump size will still leave every multiple not hitting a gap.<\/p>\n This leads to the solution that the number is a divisor of one or more of the end values of a gap.\u00a0 So for each end value we check each plausible divisor to see if it works for the entire set of gaps.\u00a0 You can set an upper bound for the divisor by calculating the floor of right edge divided by width – but if the width is 1, this upper bound doesn’t help much.\u00a0 Checking the divisors I kept everything in integers, basically doing simple fraction math rather than using floating point.\u00a0 However I didn’t notice that my cost of checking whether a divisor worked or not wasn’t O(N) where N is the number of gaps but was instead O(D) where D is the maximum distance from the start to a right gap edge.\u00a0 Since the upper bound for D was 30k and N was 50 – this was a significant performance penalty.\u00a0 The algorithm is O(N^2D) if implemented correctly, but mine was instead O(ND^2).\u00a0 O(N^2D) was fast enough to pass tests.\u00a0 I saw an O(ND log ND) implementation which passed, but I don’t actually understand why it works…<\/p>\n The mistake I made which caused the O(D) performance when checking if a specific length worked was that I incremented the multiple counter by 1 while the current location was in front of the current gap.\u00a0 If the first gap was very late, and the gap size under consideration was 1, it would tight loop increment that counter all the way up.\u00a0 I needed to either use a simple division short circuit to accelerate to the greatest multiple before the current gap, or instead use a modulus check to see if the jump size would end up in the gap rather than walk my way up at all.<\/p>\n Q3) Given a rectangular grid which is cyclic in nature (left edge joins to right edge, and top edge joins to bottom edge) where each cell in the grid specifies a direction (either left, right, up or down), determine the minimum number of cell changes required such that every cell is part of a cyclic path which comes back to itself.<\/strong><\/p>\n A3)\u00a0 This problem is a tough one. (The system tester thought so as well, it refused to rate anyone on this problem the first time round :P)\u00a0 I heard one competitor saying it was a case of min cost max flow – and I think I see how that could be the case, but min cost\/max flow is a very complicated algorithm to try and implement during the competition.<\/p>\n The first level of analysis on this problem is pretty straight forward – if every cell has another cell pointing to it, then every cell is in a cycle.\u00a0 Correspondingly every cell which has multiple cells pointing to it, has to have changes occur to reduce it to one.\u00a0 The problem is how to minimise the number of changes required to get each case of excess inputs redirected to a location of insufficient inputs.<\/p>\n A bit of thought has failed to help me construct the appropriate min cost max flow graph to solve the problem, but it is after 7am – it is time to get some more sleep…<\/p>\n Post sleep – I can see how to formulate this as min cost circulation problems.\u00a0 Each node is duplicated, with a minimum and maximum flow of 1from copy 1 to copy 2 (and a cost of 0) – then each copy 2 connects to copy 1 of its neighbour with maximum flow of 1 and a cost of 1 if it isn’t the neighbour the node currently points at.\u00a0 One special node is added, post source which connects to every copy 2 with maximum flow of 1 and cost of 0.\u00a0 Source connects to post-source with maximum flow equal to target cycle count and cost of 0.\u00a0 All copy 2’s connect to sink with maximum flow of one and cost of 0.<\/p>\n The problem is then repeated for each target cycle count between 1 and V\/2 – and the minimum of minimum costs is the result.<\/p>\n The problem is the standard min-cost max-flow algorithms don’t support minimum flows.\u00a0 One solution in this case where minimum flow equals maximum flow is to make it ‘cheaper’ to go through every minimum flow edge then any other path that doesn’t include them.\u00a0 To do this we change the edges with minimum flow to have no minimum flow but a negative cost greater than the number of edges in the original graph – this ensures that minimum cost will pass through every one of these edges.\u00a0 In this case the shortest augmenting path algorithm has to be one which handles negative cost edges.<\/p>\n One refinement – not sure if I’ve considered this before or I am just starting to understand better for the first time – but in this case you can do all of the V\/2 problems at once by setting the target cycles to infinite and keeping track of the cost after each augmenting flow.\u00a0 Since each augment is minimum cost and increases flow by 1, it will pass through every cycle count and their associated minimum cost.<\/p>\n","protected":false},"excerpt":{"rendered":" So pre challenge phase I was on 531st – with the feeling that things could go either way for me – the 500pt had the opportunity for lots of failures because of floating point error margins, which I was confident I had taken care of – but on the other hand, a small missed optimisation … Continue reading TCO13 R1A<\/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-603","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\/603","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=603"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/603\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=603"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=603"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=603"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}