So, having been knocked out in Round 2, I didn’t have to wake up at 2am to do this round, which is good because I’m not sure I would have gotten any points anyway…\u00a0 As usual, there were 3 questions, but no one solved question 3 and only 5 people successfully solved question 2, meaning you could advance to the finals with just by solving Q1 quickly and a successful challenge or 2.<\/p>\n
Q1) Given a set of 32bit numbers, determine whether each of a second set of 32bit numbers is in the resultant of K rounds of expanding the the set using the bitwise and operation.\u00a0 Specifically, every pair in the set is anded and the result is added to the new set, the input and output sets can contain duplicates.\u00a0<\/strong><\/p>\n A1) So, my initial thoughts were around that the and operation is rather limiting, so the total count of numbers will never get very large, so you could just simulate the problem, collecting duplicate outputs into counts.\u00a0 But that would be mistaken. using an appropriate set of initial numbers you can generate a very large set of outputs even once you apply distinct, and as a result simulation will take too long.<\/p>\n So, K=1 is easy, you just consider every pair.\u00a0 K=2 there are 2 cases, the 2 input numbers are either from distinct original pairs (N choose 4) or they are from overlapping original pairs (N choose 3).\u00a0 K=3 there are more scenarios.\u00a0 8 distinct original numbers anded together is the maximum, you can obviously do scenarios for 7, 6, 5, 4.\u00a0 What is interesting is that you can still do 3.\u00a0 In the K=2 case, each scenario of N choose 3 can be created 3 different ways.\u00a0 ((1,2) (2,3)) ((1,3) (2,3)) ((1,2) (1,3)).\u00a0 Since all duplicates are kept this means that these would be anded together pairwise to create another 3 new copies of each case of (N choose 3).\u00a0 From there on it follows that every possible combination involving at least 3 and at most 2^K distinct original numbers will be in the output.\u00a0 And since the original input is at most 16 numbers, we can consider every subset easily enough.\u00a0 We just need to remember to special case K=1, as it is the only case where you can choose pairs.<\/p>\n Q2) Given a NxN array with 3 specified positions on the edge being important, determine the minimum number of filled in positions which need to be added (some may already be filled in) such that there is no path of connection between any pair of the 3 original specified points (path consists of horizontal and vertical only, no diagonals).\u00a0 If there is no way to do this is less than 100 positions, return 100.<\/strong><\/p>\n A2) The ‘100’ limit is a misdirection, other than when any 2 of the specified positions are adjacent (and hence cannot be blocked) the maximum answer is 6, 3 for each of 2 of the original positions required to surround them against an edge – the 3rd position doesn’t matter of course once 2 of them are blocked in.\u00a0 However, considering the cases of placing 1-5 options on a 20×20 grid, and for each case performing a connection check is 400^6 operations in the worst case, which is far too many to complete in the few second time limit.\u00a0 It is quite feasible to check each single location, or even each pair, but beyond that is pushing your luck.<\/p>\n Looking at the 5 successful solutions they all seem to use the same kind of approach.\u00a0 The idea is to think about the minimum cost to create a wall between 2 points.\u00a0 Then the final result is either 2 walls which each block in 1 edge location, or 3 walls which meet in the middle.\u00a0 The minimum cost to create a wall between 2 points is a graph problem where a block already filled in creates 0 cost edges for the paths it blocks, a block not filled in creates 1 cost edges instead.\u00a0 The net result is you can run all pairs shortest path.\u00a0 Once you have the all pairs shortest path, you can then consider each centre location, and for each of those consider the shortest paths to create three walls from there to any location on the edge between each pair of the 3 selected edge locations.\u00a0 Finally you can choose each pair of edge positions and choose the cheapest 2 walls which go from one side of a selected location to the other. (The 2 cheapest selected must obviously be for different selected locations.)\u00a0 Choose the best result out of all of these scenarios and, presto you have the answer.\u00a0 In the worst case of a large empty map with 3 spread out selected edge locations the 2 walls will always win out, but on a map which is already filled in much more significantly, the 3 walls meeting is more likely.<\/p>\n Q3) There is a set of m positive integers , n of which are between 1 and t inclusive, and the sum of all m is less than or equal to s.\u00a0 Determine how many sets satisfy these requirements (returning count modulus large prime).\u00a0 Constraints, n is at most 100 less than m, t is at most 10^5, m is at most 10^9 and s is at most 10^18 and is at least n*t.<\/strong><\/p>\n A3) So I don’t have any answers to fall back on here, what I find most interesting is the constraints, they are rather detailed – s being at least n*t for instance is suspicious.\u00a0 Looking at this problem I see possible approaches with running times of at least O(s) which is obviously out of the question.\u00a0 The combinatorics certainly seems beyond me at the moment.<\/p>\n","protected":false},"excerpt":{"rendered":" So, having been knocked out in Round 2, I didn’t have to wake up at 2am to do this round, which is good because I’m not sure I would have gotten any points anyway…\u00a0 As usual, there were 3 questions, but no one solved question 3 and only 5 people successfully solved question 2, meaning … Continue reading TCO13 R3A<\/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-698","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\/698","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=698"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/698\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=698"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=698"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=698"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}