Attendance not that high again, 1279 registered competitors for this rescheduled round. But at least the servers seem to be more stable tonight (even if I am no less sleepy).<\/p>\n
6 Australians this time.\u00a0 I guess one of them had difficulty connecting last night.<\/p>\n
Tough round – I only submitted a solution for Q1, and I had low confidence, since it was a greedy solution and I could see the vague potential for non-greedy answers.\u00a0 During challenge phase, 40% of submitted solutions to Q1 in my room were successfully challenged, including mine.\u00a0 I was too tired to identify bugs in other peoples code however, which left me with 0 points.<\/p>\n
Which given the round difficulty was 560th before systests.\u00a0 This raised to equal 441st in the final tally.<\/p>\n
Only 2 successful solutions to Q3, and both of those people skipped Q2.\u00a0 Only ~30 solutions to Q2.\u00a0 Cut-off to advance was a fast time on Q1 and a successful challenge.\u00a0 Looks like John Dethridge and nabbftw might be in with a t-shirt chance from this round with a decent Q1 time – and EvgeniSergeev managed to get a successful challenge, the other 3 Aussies (including myself) left on 0.<\/p>\n
Too tired to do any more write up now – I’ll try and come back to it later.\u00a0 But I do at least know why my Q1 answer failed.<\/p>\n
Q1) Given 2 equal length sequences of letters, determine the correlated sub-sequences which when appended give the maximal result.<\/strong><\/p>\n A1) I have managed to fashion a ‘brute-force’ solution which passes system tests, but I’m not 100% happy that it is actually correct.\u00a0 But I will present it here anyway.<\/p>\n The first thing I did was trim the first sequence so that it was in non-ascending order – performing the matching trims in the second sequence.\u00a0 It seems trivial enough to me that if your first subsequence ever increases, you could have removed the previous lower characters to get a better value.\u00a0 The problem then seems to become a question of how best to ‘cross the append’.<\/p>\n I identified a few different ways that you could cross the append, and brute forced them.\u00a0 Each way basically starts at some offset in the first sequence and tries to cross at some letter value.\u00a0 Each letter which gets in the way (is lower than the desired cross value) is removed as it is encountered – and as each letter is removed we check to see if we’ve found a better solution.\u00a0 However there is one exception, once you have crossed over, if a letter is in the ‘way’ it may correspond to a letter in the first sequence with value higher than your starting index, in which case removing it can never be a win.\u00a0 These letters are just left in place and hope they don’t make the solution worse.\u00a0 Every combination of offset and possible cross letter value is tried and we return the best we can find.<\/p>\n The way I handle this exception lowers my confidence in my solution a lot – but it works well enough for system tests.<\/p>\n A better solution is dynamic programming.\u00a0 The DP is ‘best solution of length n using the last k characters’.\u00a0 Initialized with length 0 being empty, each iteration we check the kth last character to see if it makes a better solution to length n+1 (than the previous length n+1 solution, if one exists) by pre-pending it to length n. (Proof of correctness of this still isn’t entirely obvious, I suspect a similar solution to ‘best solution of length n using the first k characters’ would fail – since an obviously correct solution would need to apply arbitrary subsets to jump from multiple iterations before to the new iteration, rather than being based purely off the previous iteration.\u00a0 Something to do with prefixing vs postfixing would seem to be the key.)<\/p>\n Q2) Given a square grid, where each cell can be any value 0 through 9, and up to 10 specified values, determine the number of scenarios which exist where each row and column adds to the same number modulo 10. (Answer given modulo large prime.)\u00a0 The grid may be large, up to 1000×1000.<\/strong><\/p>\n A2) This problem boils down to 2 cases.\u00a0 Firstly the width of the grid may be larger than the number of given clues.\u00a0 In this case the answer is 10^((n-1)*(n-1)-k + 1) – where n is the width of the square grid and k is the number of specified values.\u00a0 Since the number of specified clues is less than the width of the grid, there exists at least 1 row and column which is completely independent of the specified values, which can be used to guarantee whatever desired modulo for each row\/column.<\/p>\n This leaves the case where we don’t have an independent row and column.\u00a0 But we do have a maximum grid size of 10.\u00a0 We can break this down further.\u00a0 First if any row or column is fully specified, we know the target modulus.\u00a0 If there are 2 target modulus that don’t match, there is no solutions, and we can immediately return 0.\u00a0 If there is no target modulus, we try and see how many solutions there are for each potential target modulus and add them all together.<\/p>\n Looking at someone else’s solution I see that from here we can break the problem down in to independent subsets.\u00a0 If a cell is not specified, than that row\/column pairing are not independent as they are linked by the choice to be made.\u00a0 But if the value is specified, then you can just subtract that value from the target for that row\/column and they remain independent.\u00a0\u00a0 A disjoint set tracker can be used to identify these independent sets of rows\/columns, and the number of possibilities for each independent set can be multiplied together to get a result.\u00a0 Once we have an independent set of rows and columns, there is either no solutions or lots of solutions.\u00a0 If there is lots of solutions, the number of solutions is much like the original calculation, 10^((r-1)*(c-1)-k), where r is the number of rows in the independent subset, c the columns, and k the number of fixed values in those rows\/columns.\u00a0 So all that remains is to identify when there are no solutions.\u00a0 This appears to be possible to do by looking at the fixed values in each row for columns which are independent, and for each column for rows which are independent.\u00a0 If the sum of each of these don’t have the same modulus, there is no way to set the values. (How you derive that leap of logic, I am unsure… but it sounds vaguely familiar from magic squares – sum of the sums each have to be equal.)<\/p>\n I wondered if a simpler solution is for a given target modulus, go to each value, set it to 0, perform any cascades forced by the modulus, and for each value you manage to set to 0, that is an extra power of 10.\u00a0 If you ever get to a contradiction, its not possible.\u00a0\u00a0 To check, I wrote this up, and it passes system tests.\u00a0 Written correctly it is O(N^4) and with N at most 10 this easily runs in time. (The more complicated algorithm above appears to be O(N^3).)<\/p>\n Q3) Given 2 numbers A and B, determine the number of unique values X^Y where 1 <= X <= A and 1 <= Y <= B.\u00a0 A and B are both potentially large.<\/strong><\/p>\n A3)\u00a0 I think I almost had a better chance of solving this problem than Q2.\u00a0 Although that isn’t saying much given how tired I was.\u00a0 We start with A*B scenarios, and start subtracting off duplications.\u00a0 With each of A and B being up to 1 billion, obviously duplications need to be removed in batches.\u00a0 The first trivial set of duplications is X=1, there are B-1 of these.\u00a0 Now we only have to consider X > 1.\u00a0 We need to identify scenarios of X^Y = N^M.\u00a0 Cases where N is a power of X aren’t too bad, but there are cases like 8^2=4^3 which are far more problematic.<\/p>\n So, taken from someone else’s solution… For each value between 2 and the sqrt of A inclusive, consider every power not greater than A.\u00a0 For every number between 2 and A inclusive not in this set there are B options.\u00a0 There is also the 1 extra for the value 1.\u00a0 What remains is how many contributions count from the others, numbers which have powers less than or equal to A.\u00a0 If we take each unique non-power in the range 2 to sqrt of (A) inclusive, and consider how many powers of it exist which are less than or equal to A we can work out how many unique values we can reach using an exponent of at most B.\u00a0 Each power can add B, but then we have to remove the overlaps.\u00a0 It almost looks like a standard add everything, remove pairwise overlaps, add back in the triplets, removing the 4’s, etc.\u00a0 But since the power could go up to 30, there are a lot of groups of 15, so it needs to be done a bit smarter.\u00a0 I can’t really work out how to describe the solution here properly, so if you are interested I guess you can go read a solution.<\/p>\n","protected":false},"excerpt":{"rendered":" Attendance not that high again, 1279 registered competitors for this rescheduled round. But at least the servers seem to be more stable tonight (even if I am no less sleepy). 6 Australians this time.\u00a0 I guess one of them had difficulty connecting last night. Tough round – I only submitted a solution for Q1, and … Continue reading TCO13 R2A (take 2)<\/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-638","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\/638","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=638"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/638\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=638"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=638"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=638"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}