As is typical for GCJ – qualifying round had a large turn out, ~22000 people made a successful submission, of those 17059 qualified (at the moment at least).<\/p>\n
63 perfect scores – 2 of which were Australian, and I don’t recognize either handle.\u00a0 Radeye gets the unfortunate distinction of 64th place, having managed to solve all of the hardest problems, but having the large input on the trivial first question fail… (I have to wonder if he was trying the different language for small\/large input thing, as his small input in perl looks fine at first glance… but it is perl, so yeah…)<\/p>\n
Q1) Do some simple analysis of a board from a 4×4 equivalent of\u00a0 tic-tac-toe where there is a special piece which counts as both X and O. Determine winner\/draw\/incomplete.<\/strong><\/p>\n A1) This problem was so trivial they had to point out not to make it harder on yourself by attempting to determine inevitable winner\/draw.\u00a0 Small and large input, but the only difference was the number of test cases. (Importantly, solving this problem completely is not enough to advance to round 1.)<\/p>\n The problem also specifies that the board will be from a valid game, so you don’t have to handle cases where both X and O have won.\u00a0 Check each row\/column\/diagonal for either winner – return if found.\u00a0 Otherwise return draw if board is full, incomplete if not.<\/p>\n Q2) Given a rectangular array of ‘heights’ and a device which reduces all heights in a row, or column above an adjustable setting, determine whether the given heights could be obtained if everything started with equal height (which is greater than or equal to anything in the given heights).\u00a0 Adjustable setting can only be changed in between usages, not as it performs a row\/column ‘trim’.<\/strong><\/p>\n A2) The important thing to notice here is that for any given square, it doesn’t matter what order the device interacts with it, it only matters what the minimum setting was across all interactions.\u00a0 So if we can determine what height was used for each row\/column – we can just run a simulation and check whether the input matches expectation.<\/p>\n For each row\/column – the device cannot have been set any lower than the highest member of that row\/column.\u00a0 And if it was set any higher, the usage definitely could have been ignored entirely.\u00a0 Therefore you can just determine the maximum value for each row\/column – perform that simulation, and check result versus input.\u00a0 This runs in O(nm) time and additional space.<\/p>\n A slower alternative (which I thought of first – and have not verified is actually correct…) is for each cell, check to ensure that it is the highest value of either the row, or column (or both).\u00a0 If it is not the highest value of either the row or the column, it cannot possibly work.\u00a0 Trivial implementation here is O(nm*max(n,m)) – which would still be fast enough (and requires no additional space, if you cared for some reason).\u00a0 This can also be done in O(nm) by painting cells which are equal to max of row, or max of column in two passes over each row\/column.\u00a0 If all cells are painted, you have succeeded.\u00a0 But the boolean for each cell has to be stored somewhere.<\/p>\n Q3) Determine the number of palindromic squares of palindromic numbers there are in the range A to B. Maximum value of B either 1000, 10^14 or 10^100 depending on problem tier.<\/strong><\/p>\n A3) This is the first time there has been a problem with 2 large inputs, one harder than the other.\u00a0 This problem was correspondingly worth a very large number of points.<\/p>\n The small input is trivial.\u00a0 In fact you can do it in your head, since the number of palindromes less than sqrt(1000) is about 12, and of those only 5 are still palindromic when squared.\u00a0 So just search the set 1, 4, 9, 121, 484 against each given A, B pair to return a count.\u00a0 I wonder if go-hero.net has a category for the null programming language…\u00a0 There was only 100 test cases, if you type fast and pre filled the form a bit, it shouldn’t be too hard to do that in 4 minutes.<\/p>\n The first large input poses a bit more of a challenge.\u00a0 The first thing to realise is that these numbers are very rare, so we can solve all 10000 test cases by generating the list once and performing binary search to find indexes to take difference to get the count.\u00a0 Indeed we could even pre-calculate the list and hard code it in this case, there aren’t that many less than 10^14.\u00a0 An approach which works for this case is generating all palindromes less than 10^7, squaring each one and checking whether its a palindrome.\u00a0 We can even generate all palindromes less than 10^7 by brute force, checking every number to see if it is a palindrome – it should still run in time.<\/p>\n The second large input is where it gets tricky.\u00a0 The numbers are still rare enough that you can calculate them all before running any test and keep them all in memory, but generating them all becomes a bit more time consuming.\u00a0 First off, we can’t possibly brute force 10^50 numbers to find palindromes to square, so instead we build the palindromes by taking the 10^25 numbers and either reflecting after or through the last digit to create our\u00a0palindromes.\u00a0 2*10^25 however is still way way way too many.\u00a0 But if you look at the output of such a program for up to 10^8, you can get a pretty confident grasp on some ways to speed things up.\u00a0 The only case where a digit greater than 2 is used in a palindrome which when squared still gives a palindrome – is 3 itself, giving 9.\u00a0 So you can special case that and this means you are down to 2*3^25 cases.\u00a0 This is still too many, but it is a big improvement.\u00a0 A closer look will show that the digit 2 is only used in very rare circumstances.\u00a0 If it is the first digit, all other digits are zero, or the last digit is 1 and is reflected through rather than after.\u00a0 Otherwise it can be the last digit that is reflected through.\u00a0 The former gives 1.5 cases per power of 10, a tiny number. The other reduces us down to 3*2^25 cases.\u00a0 This is 100 million cases, each of which is worst case performing a 50 digit by 50 digit multiplication.\u00a0 This may take minutes even with a good BigInteger implementation – so advisable to test before hand to see if it will be fast enough, or even better – pre-compute and store\/load it.<\/p>\n However, we can do better.\u00a0 A closer look shows that every palindrome which is still a palindrome when squared, the sum of the squares of its digits is at most 9.\u00a0 This is why 3 only appears once, and why 2 is so rare.\u00a0 But it does help us beyond that.\u00a0 Out of the 2^25 scenarios from creating patterns of 0s and 1s – we can skip everything which has more than 5 1s, or more specifically 4 1s in the reflected section and optionally a 1 in the middle.\u00a0 This gets us closer to 3*25^4 which is clearly going to run in time.\u00a0 But the complexity of walking permutations like this might be a little bit annoying…<\/p>\n Q4) There are a set of boxes, which each take a specific kind of key to open.\u00a0 They break the key in the process.\u00a0 Inside the boxes there may be more keys.\u00a0 You start with a set of keys and a description of all the boxes, return the canonical opening order to open them all, if possible at all.<\/strong><\/p>\n A4) Small input wasn’t too bad here, 20 boxes.\u00a0 For a given subset of the boxes being open the number of keys you have left doesn’t depend on what order you opened them, so you can do a depth first search on the canonical order, ignoring any states you find twice.\u00a0 This is O(n*2^n) which for 20 is perfectly fine – especially with only 25 test cases to perform.<\/p>\n Large input however was 200 boxes.\u00a0 The previous algorithm is no longer any good.\u00a0 I spent some time thinking about this, but couldn’t come up with a convincing idea.\u00a0 My best thought was that maybe if you did a reverse depth first search, from the answer back to the start, it might be self-pruning to the point where your search space ends up being much smaller than 2^200.<\/p>\n Looking at other peoples code, it appears that the solution is that there exists a much faster method to determine whether it is still possible to get to the final state from any given state, compared to finding a solution.\u00a0 This method is then just applied iteratively every time you try to make a move in the depth first search on canonical order, and back track immediately if the ‘can still finish’ function returns false.<\/p>\n There appears to be two parts to this approach.\u00a0 One is that you first check that there are enough keys in the given situation to open every chest.\u00a0 So you just add up the contents of every chest with the starting scenario and ensure it is higher than the count of the number of chests for each key type.\u00a0 Somehow, having checked this then makes the following seemingly nonsensical ‘can still finish’ function valid.\u00a0 Create a directed graph connecting each key type of a chest not yet opened, to the key types contained in those unopened chests.\u00a0 Then for each key type you have (ignoring count) start traversing the graph using a simultaneous breadth first search.\u00a0 If you can reach every key type used by an unopened chest – the problem is still solvable.<\/p>\n I actually wonder if some of the solutions I am reading are actually correct, or whether the fact that there was only 25 test cases meant it was easy to fake a truly correct answer.<\/p>\n","protected":false},"excerpt":{"rendered":" As is typical for GCJ – qualifying round had a large turn out, ~22000 people made a successful submission, of those 17059 qualified (at the moment at least). 63 perfect scores – 2 of which were Australian, and I don’t recognize either handle.\u00a0 Radeye gets the unfortunate distinction of 64th place, having managed to solve … Continue reading GCJ13 Qualifying Round<\/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-651","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\/651","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=651"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/651\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=651"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=651"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}