No t-shirts for me this year…<\/p>\n
Only 760 out of 850 potential contestants turned up, and I came 443rd, short of the required top 350 which advance to shirt round.\u00a0 I think 7 Aussies qualified for this round, but only 6 registered.\u00a0 Out of those 6, 3 failed to get any points (possibly fell asleep!), 2 of us around the 440th place, and John Dethridge advances 315th place.<\/p>\n
I could have made it through to get a t-shirt, but I took too long to realise I had an overflow bug in my count number of powers of k less than or equal to n loop.\u00a0 I really should have implemented it using a divide, but also I should stop using 32bit integers – except where absolutely needed.\u00a0 One day I will learn!<\/p>\n
I had time enough to do question 2, but it was not easy and I was very tired.\u00a0 I looked for corner cases for Q1 hoping to get the single challenge I needed to get through, but the given examples covered all of them, so there was basically no one to challenge.<\/p>\n
Q1) How many boolean sequences of length n are are plausible, if the ith entry is the answer to whether a number is divisible by i.\u00a0 Return answer mod 1000000007 since input can be up to 1000000.<\/strong><\/p>\n A1) I was a bit slow in realizing the correct approach here, but it wasn’t too long before I realized the answer was related purely based on the primes less than or equal to n.\u00a0 Specifically each prime doubled the answer at a minimum, more if different powers of that prime were less than n as well.\u00a0 More specifically if the maximum power of a prime p less than or equal to n is p^k then the prime independently contributes (k+1) ways to build the final sequence.\u00a0 So, multiply all these factors mod 1 billion and 7 and you have your answer.<\/p>\n What kept me too slow to advance was it took a long time to realize that my loop for determining max power was potentially squaring numbers just less than 1 million, which doesn’t fit into 32bit integer.\u00a0 I had correctly identified that I needed to use 64bit integers for the result as small powers go more than squared and so mod 1 billion and 7 is not sufficient to keep you under 32bit limit, but I should have used them more liberally from the start.<\/p>\n Q2) Given an square array of strings which are built up by concatenating the smallest of the vertically and horizontally previous cells in front of the largest, where the first row and column are provided (and each have a single character in each cell), return up to 50 characters starting at a specific index of the string in the far bottom right corner (the largest string).\u00a0 Note: no character will be repeated in the first row or column.<\/strong><\/p>\n A2) Pascals triangle gives the length of each cell – and with a worst case of 30×30 the length of the largest string can be very large!<\/p>\n Having built up pascals triangle, all that is really needed is to know for each cell, which of the two vertically and horizontally previous cells is lexically smallest.\u00a0 As usual, ‘all’ is of course the whole actual problem.\u00a0 I thought I was on the right track for this, but I suspect its performance is too slow, the trick being to define a memotizable recursion which doesn’t require an offset and length for comparison for both cells involved.<\/p>\n Edit: Before I managed to fall asleep I think I solved this.\u00a0 The memotizable recursion is ‘which is smaller for 2 cells on a common diagonal?’.\u00a0 If the 2 cells are neighbours on a diagonal, they are built out of the 3 cells on the previous diagonal. From there it can be seen that the middle cell can be ignored as it is either the common start, the common end or transitive property applies and you can just compare the outside pair.\u00a0 If they are not neighbours, you get 4 cells which are in neighbouring pairs.\u00a0 By using the memotized recursion on each neighbouring pair you can then reapply the recursion on the smallest of each pair.\u00a0 Memotization ensures that the algorithm runs in O(n^3), both in space and time.<\/p>\n Now if you can read between the lines there you’ll notice that I have failed to take in to account an important special case.\u00a0 Once the recursion hits an edge we need to compare that edge value to a cell on the same diagonal.\u00a0 Unless that other cell is on the opposite edge of the diagonal, this doesn’t appear trivial.\u00a0 However the original problem was ‘determine the nth character in the bottom right hand corner’, we can trivially expand that to also ‘determine the first character in every cell’.\u00a0 Since the answer to these new questions depends on the which is smaller question, it might seem we are at an impasse – but because each question is entirely answered by considering the previous diagonal alone, we can invoke mutual memotized recursion safely.<\/p>\n All that remains is to prove that this method works.\u00a0 Something which is obvious is that each cell is only made up of characters which appear on the edge in the same or lesser row, or same or lesser column.\u00a0 Thus since every comparison in the algorithm involves two different cells on the same diagonal, it can be seen that the termination comparison is never equal, as an edge on a diagonal compared to a different cell in the diagonal cannot be equal as the cells on the diagonal cannot be made out of that edges character and all edge characters are distinct.<\/p>\n Q3) Given 2 arrays of positions, and a set of ‘connections’ from one array to another, determine the number of orderings of the two arrays such that no connections cross. (Return mod 1000000007 as with arrays of length 50, the answer might be very large.)<\/strong><\/p>\n A3) Edit: Also solved this one before going to sleep.\u00a0 I think it is easier than Q2 even.<\/p>\n First step, DFS the connections to form them into groups.\u00a0 If you discover a loop, return 0.\u00a0 Now we have our first factor in the answer, n! where n is the number of groups.\u00a0 Each group is going to be independent, since there is no way they can cross each other without causing a crossed connection so the n! comes from the orderings of the n groups.<\/p>\n Each group now contributes an independent factor.\u00a0 There are 2 scenarios, either every edge in the group joins at a common endpoint, or there are 2 or more locations in the group where 2 or more edges join.\u00a0 If it is a single common endpoint the answer is k! where k is the number of edges in the group.\u00a0 If it is more than two common endpoints we can either arrange said endpoints left to right, or right to left – so that gives a factor of 2.\u00a0 Then for each endpoint we also get a factor of (m-2)! where m is the number of edges which join to that endpoint.<\/p>\n Finally we have additional factors for the array locations which do not participate in a connection.\u00a0 These can be added in any place in any order, so if there are n spots in the array and k of them are endpoints of 1 or more connections, the additional factor is n!\/k!.\u00a0 Since there are 2 arrays, this gives 2 more factors total.\u00a0 Multiply everything together using repeated modulo and 64 bit integers… and we should be done.<\/p>\n All in all it makes me wish I was less tired when I did the competition.\u00a0 I think I could have solved that second question during the competition if I had of been able to concentrate at all.\u00a0 Third one, well I’m pretty sure I would have run out of time having only opened it with a few minutes to go.<\/p>\n","protected":false},"excerpt":{"rendered":" No t-shirts for me this year… Only 760 out of 850 potential contestants turned up, and I came 443rd, short of the required top 350 which advance to shirt round.\u00a0 I think 7 Aussies qualified for this round, but only 6 registered.\u00a0 Out of those 6, 3 failed to get any points (possibly fell asleep!), … Continue reading TCO11 R2<\/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-416","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\/416","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=416"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/416\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=416"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=416"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=416"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}