Out again in round 2.\u00a0 Last year in ~800th, this year in 1263rd. So again no t-shirt from Google.<\/p>\n
I am a bit disappointed with my effort, the answer to question 3 had been staring me in the face for an hour, but my late night addled brain just refused to see it.\u00a0 If I had of seen it, I think I could have even solved the large input and made it through to round 3.\u00a0 Maybe I would have seen it if I had of spent a few more minutes on it rather than doing question 2 small input.<\/p>\n
Q1) If you are in a corridor of a certain length, and there are moving walkways some or all of the length of that corridor, and each walkway has its own speed boost which it applies to your speed, and you can walk at a speed S and run at a speed R, but you will run out of puff if you run for longer than T total, what is the shortest time to get from the start of the corridor to the end?<\/strong><\/p>\n A1) This problem was very easy, although it was a bit fiddly.\u00a0 The key to notice is that you want to run during the period of time that your walking speed + walkway speed is slowest, as that has the greatest net effect on the final time.\u00a0 So, just sort the input by walkway speed, run on all non-walkway bits you can, then on the walkways in the order they are now sorted.<\/p>\n Q2) Given an rectangular array of point masses, where each mass is given as a deviation from the smallest mass (and no deviation is more than 9 units), determine the largest square array of these point masses, which if you remove the 4 corners has a centre of mass at its actual centre.<\/strong><\/p>\n A2) Again, simple enough, but the brute force attack (which is what I implemented to try and get a few more points) is O(N^5) and the large input is up to 500×500.\u00a0 The key is to do a bunch of pre-calculation of moment of mass and sum of mass of every rectangle array starting from the top left corner, about (0,0) in O(N^2) time by using the fact that moment of mass and mass is additive, a larger rectangle can be determined from the sum of the rectangles 1 smaller in each dimension individually, minus the overlap, then finally tacking on the new mass element.\u00a0 Once these pre-calculations are done, any rectangle can be calculated quickly by adding the bottom right corner and top left corner, and subtracting the bottom left and top right corners.\u00a0 Then finally this can be adjusted by taking off the corners.\u00a0 And to finish off we can check whether the centre of mass is in the middle by seeing whether the moments are equal to the product of total mass and the centre position.\u00a0 Since there are O(N^3) scenarios to check, and they can now all be considered in O(1) time, the 500×500 isn’t too bad at all.<\/p>\n All in all, this question was perfectly doable, but I had decided to focus on question 3 for too long to come back and think about it properly.\u00a0 If I had of done this problem I suspect I would have implemented a different approach.\u00a0 Consider the number of 1xn and nx1 subsections of the input.\u00a0 There are O(N^3) of these, which can each be calculated in O(1)\u00a0 by building off each previous 1x(n-1) (n-1)x1 sections.\u00a0 From there, each of the O(N^3) scenarios can be built up in O(1) from each previous scenario, by slapping on the rectangular edges and then subtracting off the corners twice (and adding on the previously removed corners).<\/p>\n Q3) Given an integer N, the numbers 1 to N can be ordered and then processed in the following way.\u00a0 As each number is considered, a total (starting from 0) is checked to see if it is a multiple of this number.\u00a0 If it is not, the total is increased to the smallest total which is a multiple of this number.\u00a0 If the number is no longer a multiple of one of the numbers previously considered, this process continues until all processed numbers divide into the current total.\u00a0 Throughout all possible orders what is the difference between the most and least number of times that adding a new number to consideration results in the total being increased.<\/strong><\/p>\n A3) The wording was tricky, but it boils down to how do you order the first N numbers, such that the running lowest common multiple changes the most number of times, or the least number of times.<\/p>\n I fairly quickly identified that the most number of times occurred when you process the numbers in order, further identifying that the actual answer was equal to 1 + the sum of the maximum number each prime could be raised to and still be less than N.\u00a0 That is half the problem solved…<\/p>\n However, I started by considering the reverse order, which worked correctly for small values.\u00a0 I then considered maybe ordered by the number of prime factors, but that was actually even worse.\u00a0 Finally I ran out of time with my sleep deprived brain giving in.<\/p>\n So, what was that second half of the answer?\u00a0 It comes right back to the first part, put the maximum power of each prime in first, then everything else will not change the LCM.\u00a0 I have no idea why I failed to consider this scenario, it seems so very obvious now.<\/p>\n And this leads to how to do the large input, where a maximum value of N was 10^12.\u00a0 O(N) was going to be too slow, and looking at 10^12, I had immediately thought that the answer would involve the primes less than or equal to the square root. (I even wrote the once off pre-calculation of all primes less than 1million, to be ready for needing that scenario.)\u00a0 With the minimum answer being the number of primes less than N, and the maximum answer being the number of primes, and all of their powers less than N, the difference is all of the prime powers of at least squared, which are less than N.\u00a0 Hence that array of the prime numbers less than 1million is all you need to implement a very fast answer.<\/p>\n Q4) Given a graph with unit edge distances, determine the shortest path between 2 points, which is also within 1 unit of the most number of vertexes.<\/strong><\/p>\n A4) The shortest path part of this algorithm is easy enough, the maximizing the number of vertices near the path is an entirely different story.\u00a0 Fairly obviously it will be a memotized recursion\/dynamic programming solution, but the recursion is not trivially obvious.<\/p>\n I looked up the answer because it is way early in the morning and I just wanted to finish writing this up before dawn…\u00a0 So the recursion you use is to consider the maximum number of vertexes ‘near’ the shortest path to b where the previous node in the path was a.\u00a0 This is equal to the maximum over the sum of paths ending in a with a each possible previous node before that, plus the number of additional new ‘near’ nodes which get added extending that path to b.\u00a0 This is the key point, it is possible to work out the number of new ‘near’ nodes in a path if you know the last 3 nodes of the path.\u00a0 This observation occurs because you can see that if a node next to the latest node in the path was close to anything before those last 2, then the second latest node isn’t actually on the shortest path, as it could have been skipped via this theoretical other path.<\/p>\n And in-fact doing that is actually the most time consuming part of the problem, but it isn’t exactly hard, just consider every vertex, is it next to the end of the path, if so, is it next to either of the previous 2 on the path.\u00a0 Using an edge matrix, this is O(V) for each scenario.\u00a0 Cache each triple to avoid repeated calculation, and you are done.\u00a0 (Slight optimizations exist, but are not required given the input size.)<\/p>\n","protected":false},"excerpt":{"rendered":" Out again in round 2.\u00a0 Last year in ~800th, this year in 1263rd. So again no t-shirt from Google. I am a bit disappointed with my effort, the answer to question 3 had been staring me in the face for an hour, but my late night addled brain just refused to see it.\u00a0 If I … Continue reading GCJ11 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-391","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\/391","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=391"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/391\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=391"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=391"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=391"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}