Unlike Round 2 where I think I would have struggled to make the top 500, this round I think I might have done much better if I had been competing. Possibly even top 120.<\/p>\n
Advancing to the world finals was definitely beyond me, that would have\u00a0required\u00a0solving the large of the problem worth the most points as well as the other problems I consider within my reach, which\u00a0I struggle to even comprehend how the solution verifier could work…<\/p>\n
Q1) Given a sequence of moods which you can either make a request or submission against, and the constraint that you can only submit your last unsubmitted request, determine the maximum score you can get if you get 10 points for requesting in the same mood as a submission, and 5 points otherwise.<\/strong><\/p>\n A1) The actual problem describes the possibility to get 0 points, but that would require you to request the wrong thing for the current mood and then submit it later also against the wrong mood. \u00a0Any such scenario can trivially be improved by changing your request to not be the wrong thing, since the later submission would then also not be the wrong match, so you get 10 more points.<\/p>\n So, this problem is a bit deceptive, but a little playing around with scenarios should give you a good guess that greedy is the way forward. \u00a0If the input sequence of moods has equal two in a row, you’ll do a request submit to get the 10 points. \u00a0Having removed those, you might now have moods which are neighbouring and equal, so you can align those up and get 10 points there as well. \u00a0Keep repeating until there is no pairings left. \u00a0The remains is a simply alternating sequence, there is no way to get 10 points in a simply alternating sequence regardless of the moves you perform. \u00a0So just take each pair as it comes and get 5 points each.<\/p>\n Having discovered this greedy solution, the only problem remaining is that the large is up to 20k, so an O(N^2) solution is going to be too slow…<\/p>\n As it turns out, its possible to do in linear time. \u00a0The simplest approach I have for doing this is a bit unusual. \u00a0It uses a linked list!<\/p>\n Convert the input in to a linked list, then while you have a current node and and a next node, if they are equal, remove those nodes and leave current point to either just before current or just after next if there is nothing before current. \u00a0If they aren’t equal, advance one. \u00a0Every time you remove a pair\u00a0add 5 points to your total. \u00a0Then add 5 points for half the size of the original input.<\/p>\n A more complicated approach which doesn’t technically require a linked list, would instead involve an array of starts. \u00a0When you find a pair you\u00a0repeat outwards to find the largest simple chunk which can be matched up from the inside out. \u00a0Then you set the start array for the\u00a0last member of that chunk to point to the first. \u00a0Then you move on. \u00a0Whenever you finish creating a chunk, check if its left neighbour\u00a0has a start value. \u00a0If so use that\u00a0value to conceptually O(1) merge this chunk with its neighbour and start considering whether the ones outside that can be made in to a pair. \u00a0If so, keep going and write a start value once you get stuck again. \u00a0This basically simulates the process of the linked list algorithm…<\/p>\n Q2) Determine the fraction of strings which contain\u00a0certain words\u00a0where the strings are generated by all the possible ways to select nodes of a forest such that you only ever select a child after its parent and each node has a single character label.<\/strong><\/p>\n A2) This question was probably the one I was least likely to get out even though I could solve it. \u00a0It just looks too hard…<\/p>\n In practice you just need a small number of scenarios to convince yourself that a simple answer is in fact correct.<\/p>\n Because the required accuracy is only 3 parts in 100, randomly generating 10000 of the strings should be plenty. \u00a0(The exact detail escapes me, but I seem to recall that if you require an accuracy of 1 part in x for something that has a specific random chance, you need to run x^2 simulations.)<\/p>\n Given the input size is only up to 100, O(N^2) should be ‘okay’ to generate 10k strings if you are quick about it. \u00a0The trick is just how to ensure that your randomly selected strings are representative.<\/p>\n To work this out, consider a simple case where one node is on its own, and 10 others are in a chain. \u00a0There are 11 possible outputs, for each of the different possible locations of inserting the one node in the chain. \u00a0If you were to select with equal likelihood from the available options at any point, half of your generate strings will start with the label of the one node on its own, when it should only be ~9%. \u00a0The next option I considered was randomly selecting a node and adding it and all of its parents. \u00a0However if we do that the probability of the one node on its own being the last value is far higher than 9%.<\/p>\n The third option I considered was, weighting each available node to select from, by additionally including the count of all of its children. \u00a0This means the first selection is 10 parts the chain, and 1 part the node on its own. \u00a0Which gets us the correct percentage. \u00a0Following all the way through the options shows it generates things correctly for this scenario. \u00a0Which is promising. \u00a0We already know it also generates the right values for a forest entirely of single nodes. \u00a0So that is two data points in its favour… \u00a0I tried one more scenario to convince myself. \u00a0A single node and a simple 3 node tree. \u00a0The tree has 2 orders, and the single node has 4 insertion points, this gives 8 possible scenarios. \u00a0Of those 8 scenarios 2 start with the single node. \u00a0Again the weighted selection works 3:1 corresponds to 8:2. \u00a0And walking through the rest of the scenarios shows the percentages work out.<\/p>\n Good thing about this question is that its just a high valued small input, so if this weighting thing is wrong, we can find out pretty quickly… \u00a0but its just fine as it happens.<\/p>\n So calculate the weights of the tree, then add the roots, randomly select based on total weight, remove that node, add its children, repeat. \u00a0This is O(N^2).<\/p>\n A slightly nicer to implement solution is to recognise that the weights are effectively a place holder for allowing random selection of any node and then putting the deepest not yet placed parent of that node instead of the selected node. \u00a0This way you don’t have to do any tree constructing. \u00a0Just have a boolean array representing what has been selected so far, generate a random number the size of the remnants and walk to find the nth not selected item. \u00a0Then walk its parents while they exist and aren’t selected. \u00a0Finally select that node and then\u00a0repeat the process until all nodes are selected.<\/p>\n Q3) Determine the smallest maximum jump size to get from one asteroid to a second asteroid, if there are a bunch of asteroids moving at linear speeds and you can jump between any two at any moment so long as you don’t stay anywhere more than S seconds.<\/strong><\/p>\n A3) This problem reminds me of another I’ve done before, but that was in 1 dimension, this is in three…<\/p>\n However, the small input is easy, since all the linear speeds are zero. \u00a0Therefore there is no point to waiting anywhere. \u00a0Therefore it just becomes a question of for a given maximum jump size x, is there a path between asteroid 0 and asteroid 1 then solving for the smallest maximum jump size x. \u00a0Once a maximum jump size is set, the problem reduces to a simple search (DFS is one option). \u00a0To solve for smallest, you can do a binary search.<\/p>\n Contest analysis isn’t up yet, and I’ve not ready anyone else’s solutions, so I don’t know how to do the large. \u00a0I suspect it has a similar structure. \u00a0Once you have a set maximum jump size you can determine the time ranges that a given edge is open or closed. \u00a0This appears to cause a combinatoric explosion if you clone each node based time range that a given combination of edges are open\/closed with edges between the clones depending on the size of S, but maybe you don’t need to, you can instead just have a separate clone per status of a single edge, connected to clones representing different arrival time ranges and the separate arrival and departure clones are connected depending on the times and size of S… \u00a0I don’t quite think it works though.<\/p>\n Q4) Given a simple single bit single register computer and two programs that run simultaneously made of three atomic instructions, set 0, set 1 and print register, determine a program pair which can potentially print any of the ‘good’ values, but never prints the ‘bad’ value.<\/strong><\/p>\n A4) Again I don’t know how to solve the large (at least I don’t think I do…), but the small is surprisingly trivial.<\/p>\n For the small input the bad value is always a sequence of ones. \u00a0So as long as the bad value isn’t also a good value (which is something to just check for in general…) one option\u00a0is to write a program which can print any sequence of X digits except for all ones. \u00a0One way to do this, is to have one program that continuously sets the register to 0, then prints the register, x times. \u00a0Then the second program consists of exactly X-1 calls to set the register to 1. \u00a0Because of arbitrary interleaving, this program pair can print anything except for X 1’s. \u00a0Since the first program always sets to 0 before printing, there would need to be an interleave before every print, but there are only X-1 instructions from the second program to interleave.<\/p>\n This is suggestive of possible approaches for the large, but the open question in my mind is whether they cover all possible inputs correctly, or just a subset. \u00a0For instance an input where the bad value is all zeros, can be solved using an inverted version of the program. \u00a0If the bad value has one one digit, and all the good values have either more or all less than one one digit\u00a0similar constructions work. \u00a0In general I can solve if the number of set bits is either strictly greater or strictly less than the bad value, but not otherwise. \u00a0For specific cases if there is only one good value, I can solve that too… \u00a0If there are multiple good values and they have x set bits in common, but the bad value ‘further away’ from the commonality then the good values or doesn’t have all of those values set. That can be solved too. \u00a0Or inverted for x unset bits in common.<\/p>\n In general the things I can solve are where one program does all the printing, and the second program is a sequence of ones or zeros of some length. \u00a0Its not clear to me that such a program pair is always the solution if there is such a solution, but it doesn’t seem unlikely…<\/p>\n","protected":false},"excerpt":{"rendered":" Unlike Round 2 where I think I would have struggled to make the top 500, this round I think I might have done much better if I had been competing. Possibly even top 120. Advancing to the world finals was definitely beyond me, that would have\u00a0required\u00a0solving the large of the problem worth the most points … Continue reading GCJ 2016 R3<\/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-847","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\/847","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=847"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/847\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=847"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=847"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=847"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}