Another week, another round of a coding competition… or so it seems this time of year.<\/p>\n
Top 1000 advancing to round 2.\u00a0 The cut-off was fully solving question 2 and the small input of question 1 in 2:20.\u00a0 All small inputs in a fast time came 1035th, which was interestingly close to advancing.\u00a0 The score to get by without having to worry about time was achieved by all small inputs and the large of the first question.<\/p>\n
Q1) Given a game where characters can be duplicated and consecutive duplicate characters can be collapsed back to a single character, determine if a set of strings can be made equal, and if so, the minimum number of moves to achieve this goal.<\/strong><\/p>\n A1) Determining whether the goal can be achieved is easy, just replace all sequences of consecutive repeats with a single character, and determine if all the input strings are equal.\u00a0 This produces a ‘canonical’ form that all must match.\u00a0 For the minimum number of moves it isn’t really that much harder.\u00a0 For the small input there are only 2 strings, so choose one of the strings and count how many moves it takes to make the other equal to it.\u00a0 There is no advantage to trying to meet in the middle, so on a per canonical string character basis just take the absolute difference of the counts in each of the strings and sum them all for the result.<\/p>\n For the large input there are up to 100 strings, but because each string is only at most 100 characters, no letter can be repeated more than 100 times.\u00a0 Therefore the ideal to converge upon will be no more than 100 repeats and no less than 1.\u00a0 Since each character of the canonical form can be considered independently, all possibilities can be easily tested within the time limit.\u00a0 Just try each value of 1 to 100 inclusive and calculate the sum of absolute differences, the smallest sum is the minimum number of moves for that canonical character.\u00a0 Then just sum all of those minimums for the final result.<\/p>\n The most challenging part of this question is probably that the large input is considerably more ‘different’ to the small input, so a bug in the code could easily get past the small input only to fail on the large input, even though it would easily run in time.<\/p>\n For interest, an extension of this question where the maximum length of a given string is unbounded by the maximum length of the canonical form is short, the problem is still easily solved so long as the counts are provided rather than having to parse the unbounded length string.\u00a0 The sum of a set of absolute difference functions all with equal slope has a minimum at the middle of the sorted list of 0 points of the individual functions.\u00a0 For an even number of functions, either of the middle 2 will work because the the sum is flat in between.\u00a0 Thus with a value selected the total of absolute differences can be calculated for a total run time proportional only to the number of strings and the number of characters in the canonical form.<\/p>\n Q2) How many pairs of 2 numbers selected from specific ranges when bitwise ‘and’d together have a result in a 3rd specific range.\u00a0 All ranges start from 0.<\/strong><\/p>\n A2) Easiest small input ever?\u00a0 With range sizes of only at most 1000 each, nested loop over the input ranges and calculate the and and compare to the maximum value of the 3rd range.\u00a0 If less increase counter.\u00a0 Once loops are done, return counter.\u00a0 6 trivial lines?<\/p>\n Large input however is much more challenging.\u00a0 With ranges of up to 1 billion, such brute force is out of the question.\u00a0 Given the bitwise and function and the large ranges, running time seems like it will need to be related to the logarithm of the input range maximums.<\/p>\n Determining whether 2 numbers ‘and’ to give a 3rd is trivial, which leads to the thought, is there some way to convert the ranges into batches which can be easily processed in parallel.\u00a0 Perhaps using a ternary notation of 0, 1 and ‘don’t care’?<\/p>\n All numbers less than n can be grouped in a ternary notation by having a prefix which is equal to the start of n, followed by a 0 where there is a 1 in n, followed by ‘don’t care’ for all subsequent bits.\u00a0 The number of such patterns needed is equal to the number of set bits in n, which is worst case proportional to the logarithm of n.<\/p>\n So the problem now boils down to, generate these ternary representations for the 2 input ranges and the output range, then for every way of selecting from those 3 lists, determine how many results it allows.\u00a0 Sum those all up, and return.<\/p>\n So the core part of that is ‘determine how many results it allows’.\u00a0 So inside the triple nested loop to select the 3 ternary representations being tested another loop over each bit is needed.\u00a0 Each bit is independent in the bitwise and, so the number of ways of doing each bit can be considered a multiplier.\u00a0 Multiplying them all together will give the number of solutions that are derived from this particular selection.<\/p>\n Handling each bit can be done with a large if statement selecting on the 3 different values which can be in each of the 2 inputs and the output.\u00a0 For example ‘don’t care’, ‘don’t care’, ‘don’t care’ has 4 possible scenarios and ‘don’t care’, ‘don’t care’, 0 has 3 possible scenarios.\u00a0 Such an if statement is quite large and convoluted, so some more nested loops might be simpler.\u00a0 Loop over each possibility for the 2 inputs, skipping if it doesn’t match the actual input values.\u00a0 Then calculate the and of the 2 input bits and compare it to the expected output value incrementing the counter if it matches.\u00a0 The simple match function for ‘bit vs ternary value’ is handled much more easily than the huge if statement.<\/p>\n One catch is that the 3 ranges originally specified 2 are exclusive and one is inclusive of the maximum, so applying the above approach the inclusive bound needs to be incremented to make it an exclusive bound first.\u00a0 Alternatively all numbers less or equal to n can be considered by using the same set of patterns above and adding the exact pattern of n as well.\u00a0 This is equivalent to setting the bit one past the end of the number to 0 and so can be treated as one extra loop, with appropriate special case handling.<\/p>\n Q3) Given a set of locations with distinct ‘values’ and a list of connections between locations (all locations are connected), determine a order of visiting which doesn’t arrive at any node more than once, but can backtrack as much as you like, which visits every node such that the sequence of first visits is ‘smallest’.\u00a0 Smallest is defined by comparing the first elements of two sequences, then the second elements, and so on until one is smaller than the other.<\/strong><\/p>\n A3)\u00a0 The small input only had 8 nodes, so brute force was plausible.\u00a0 Just had to make sure you don’t infinite loop.<\/p>\n First thing to realise is that the values of the locations do not matter, so first step is to renumber the graph so that the smallest value is node 0, the second smallest is node 1, and so on.\u00a0 Then the walk of the graph desired is one which prefers smaller node indexes.<\/p>\n The solution seems to be a greedy approach.\u00a0 First thing to realise is that node 0 (in the renumbered scenario) is always the correct place to start – since you can start from anywhere, and it is always possible to walk to every node of a connected graph, starting from any given node even with the additional restrictions specified by the problem.<\/p>\n From that first location you will always walk to the smallest index connected to node 0.\u00a0 But after that it becomes slightly more tricky.\u00a0 More generally the problem becomes deciding what to do when you have visited a set of nodes V and have a current path from node 0 to current node N.\u00a0 For each of the nodes on the path, you can go to any of the nodes not in V that are connected to the node in the path.\u00a0 This leads to a set of scenarios which need to be prioritized for the greedy approach.\u00a0 The obvious priority is the index of the destination.\u00a0 It is always preferable to go to a smaller index if possible.\u00a0 However we need to break ties as the graph can be fully connected, in which case it is possible to reach every node from every node.\u00a0 Here the idea is that deeper in the path is better.\u00a0 Every time you backtrack you lose the possibility of going from that node in future, so it is kind of an opportunity cost.<\/p>\n So that seems pretty simple – but just choosing the best value from the set of scenarios, doesn’t always work.\u00a0 The problem is that it may cause you to back track to take a link to a low index node, but there might be nodes that can only be reached through the node you backtracked from, and there is no way to get back to that node any more.\u00a0 Therefore before taking any option in the priority order of options, you must perform a reachability check. A recursive walk from each node in the potential future path, out in to the world not visiting anywhere already visited, do you visit every node not already visited?\u00a0 If the reachability check fails, that option must be discarded and the next highest priority considered.<\/p>\n The running time of this algorithm is a bit complicated, but an easy upper bound can be found.\u00a0 There are O(N) steps.\u00a0 Worst of these steps has O(N) nodes on the current path.\u00a0 This results in O(N^2) possible scenarios to consider.\u00a0 Each of which could require a reachability analysis which takes O(E) or O(N^2).\u00a0 Thus an easy upper bound is O(N^5) which with 50 nodes is fine.\u00a0 In practice the cases with high number of scenarios at a given step also tend to pass reachability easily, so the code runs within time with ease.<\/p>\n","protected":false},"excerpt":{"rendered":" Another week, another round of a coding competition… or so it seems this time of year. Top 1000 advancing to round 2.\u00a0 The cut-off was fully solving question 2 and the small input of question 1 in 2:20.\u00a0 All small inputs in a fast time came 1035th, which was interestingly close to advancing.\u00a0 The score … Continue reading GCJ14 R1B<\/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-749","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\/749","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=749"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/749\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=749"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=749"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=749"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}