Top 1000 advanced which looks to be solving question 1 completely and question 2 small in < 1:50.\u00a0 For safety add in the question 3 small input.\u00a0 In fact you could drop question 1 large.\u00a0 All 3 small inputs was sufficient to advance.<\/p>\n
Q1) Given a fraction, determine if it can be created by repeated pairwise averaging of 2^40 values which are either 0 or 1.\u00a0 If so, determine the best case depth of a value of 1 in that averaging. (Best case being closest to the final value.)<\/strong><\/p>\n A1) Odd little question, but actually quite simple.\u00a0 Difference between small and large input was that the large could involve 64 bit numbers, and you needed to implement a GCD to reduce the fraction to minimal components, but otherwise still quite simple.<\/p>\n The solution comes that because repeated pairwise averaging is identical to just averaging all the values at once, the fraction must be of the form n\/2^40.\u00a0 So if the base of the fraction is a power of 2, the fraction can be created.\u00a0 This is where the GCD comes in for the large input, without reducing to the minimal form, the base could be a multiple of a power of 2, and also of some other number, which can be factored out of the numerator.<\/p>\n For calculating the depth, it is obvious that if you consider the n\/2^40 form you have n 1’s at the top level.\u00a0 To keep a 1 as long as possible you shift them all to one side.\u00a0 Thus the depth will be 40 – the floor of log 2 of n.\u00a0 Another way of looking at it is that if the fraction >= 1\/2 a parent can be a 1, >= 1\/4 a grand parent, and so on.\u00a0 So the depth is equal to the number of times you can double the fraction before it is greater than or equal to 1.<\/p>\n Q2) Given sequences of characters, determine how many ways the sequences can be ordered such that the concatenation has every case of any given letter being in a single contiguous grouping.\u00a0 Return result modulo 1 billion and 7.<\/strong><\/p>\n A2) Small input there are 10! orderings to try, so it can just be brute forced.\u00a0 Large input there are up to 100 sequences, so something smarter is needed.<\/p>\n The approach I would have gone with is categorizing the inputs.\u00a0 If a sequence contains just the one character some number of times, we call that a ‘repeater’ (even if it is just a single character).\u00a0 If a sequence starts with some number instances of a letter, we say it starts with that letter.\u00a0 Similarly for ending.\u00a0 Any characters between a start and end and the sequence also gets categorized as having those characters in the middle.<\/p>\n From there a bunch of impossible scenarios can be detected straight off the bat.\u00a0 Only 1 sequence can start with any given letter, excluding repeaters.\u00a0 Same for ending.\u00a0 No 2 sequences can have the same characters in the middle, unless they are both repeaters.\u00a0 A single sequence can’t have the same character in the middle multiple times, unless they are contiguous.\u00a0 (I note now that the problem can be somewhat simplified by removing all contiguous duplications from the input sequences.\u00a0 They don’t change the problem and just complicate detecting invalid scenarios.)<\/p>\n Next the inputs need to be grouped.\u00a0 A starter and an ender of the same letter (and the repeaters) must be in the same group.\u00a0 When gathering a group, you can follow the starter to an ender, and then to a starter, and to an ender and so on, and vice-versa, to get a full group.\u00a0 However if you detect a cycle, this is also impossible.<\/p>\n The final part is to calculate the number of orderings.\u00a0 If there are n groups, those groups can be selected to form n! orderings.\u00a0 Each group has only one ordering, unless it has repeaters.\u00a0 Each letter in a group which has k repeaters, contributes k! orderings.\u00a0 All these factorials must be multiplied together, continually using the modulo 1 billion and 7 as required and use 64 bit integers to avoid overflow.<\/p>\n Q3) Given a NxM grid of points connected by horizontal and vertical lines, determine the minimum number of covered points required to enclose at least K locations.\u00a0 Enclosing is defined by either being covered or being unable to connect to the edge of the grid without going through a covered point.<\/strong><\/p>\n A3) The small input has N*M less than or equal to 20.\u00a0 This actually limits a lot of the possible scenarios, but it does allow a brute force of whether each point is covered or not.<\/p>\n The large input has N*M <= 1000, which gives a lot greater possibilities for tricky corner cases, but does easily allow for a O(N*M*(N + M)) time algorithm.\u00a0 (Examples of this can be found in the solutions to download.)<\/p>\n So this problem has a few things to it, which makes it a bit tricky.\u00a0 First of all the problem is actually slightly simpler with an infinite grid.\u00a0 In this scenario we can ask ‘what is the largest area that can be enclosed with n stones and not have to worry about whether the ideal shape runs into the edge of the grid or not.\u00a0 So if n = 4k, the ideal shape is a diamond pattern.\u00a0 Proving this may be non-trivial in practice, but it makes a lot of sense.\u00a0 In such a shape any attempt to increase the area by moving a stone, forces all the other stones to move, just moving the shape.\u00a0 If n = 4k+2 the ideal shape has 2 options, either a diamond with 2 longer opposite sides, or take the 4k ideal and duplicate 2 of its vertical or horizontal extremes, kind of making a blunted diamond.<\/p>\n When I was first thinking about this problem I made the mistake of not considering 4k+1 and 4k+3 correctly.\u00a0 Looking at the case of k=1 led me to conclude that these could only cover one extra position in terms of area compared to the one stone less case.\u00a0 Instead the ideal scenarios look more like this:<\/p>\n The general pattern that can be derived is that there are 4 diagonal lines, which either meet at a point or a blunted point.\u00a0 4k is a perfect diamond shape, 4k+1 one diagonal line moves outwards, causing 2 blunts.\u00a0 4k+2 moves out two diagonal lines, if they are adjacent then there are 2 blunts on opposite corners, if they are opposite it is all points, but the diamond is stretched.\u00a0 4k+3 moves out 3 diagonal lines, resulting in 2 adjacent blunted points on a stretched diamond.<\/p>\n So, how does this interact with the the borders?\u00a0 Well it turns out that so long as you choose adjacent case for 4k+2 (or maybe even if not?), simply truncating positions to fit inside the box is as good as you can do.\u00a0 I don’t have a good proof, but once the shape is too big, the edges have to be connected, so you get runs across the edge, and minimizing stones becomes cutting diagonals across the corners, which ends up being the same as squishing the ideal shape into the available space.<\/p>\n So the O(N*M*(N+M)) solution is to try every area less than or equal to N*M, and cut off corners incrementally until they no longer touch the edge.\u00a0 Since every area is tried, the ideal scenarios that don’t touch the edges of the full NxM grid are all tried because they are all touch the sides of some size rectangle.\u00a0 Taking turns cutting the corners off one by one goes through the 4k, 4k-1, 4k-2, 4k-3, 4(k-1) sequence, pushing the diagonal lines inwards incrementally.\u00a0 The best solution of all tried is returned.<\/p>\n A more interesting (but same running time solution) is to consider ‘can it be solved in n stones’ and then depending on the modulus the formula for the 4 boundary diagonal lines can be formulated, knowing the border will be a total of n stones, the area can then be calculated by walking over every point and checking whether it is inside the 4 diagonal lines.\u00a0 The solution I saw using this approach tested cutting off corners in both orientations of the NxM grid, but I suspect that with a little thought it could be reduced to only testing one of those 2 orientations.<\/p>\n This approach leads to an O(N+M) solution.\u00a0 Since the worst case answer is 2N+2M-4, you can walk upwards towards that value checking each n until one works.\u00a0 If you can calculate the covered area in O(1) time, this is O(N+M).\u00a0 This is much more complicated piece of code, but by calculating the intersection points of the 4 boundary lines with each other you can calculate a reduced area (if the shape isn’t already going to touch the edges) and then the number of empty points in the corners of this possibly reduced area can be calculated by k(k+1)\/2 where k is the index (counting based on 0 from the corner) of the first filled in point along the edge, which is found by calculating the intersection of the diagonal line with the edge.\u00a0 The sum of these 4 corner cut-offs is subtracted from the the total area to give the number of enclosed points.\u00a0 There are 4 diagonal line pair intersections and then 4 diagonal line with a edge intersection calculations involved, all of which are simple formula solves (although the blunted corners result in the ‘intersection’ of the 2 lines being somewhere between points where you can place a stone, this is easily special cased) which can be done in O(1) time, for a total of O(1) time to calculate the covered area.<\/p>\n Special cases.\u00a0 If the desired area is 4 or less, no need to do any work, the number of stones required equals the area.\u00a0 This is also the case if the minimum of N and M is <= 2, since there is no way to surround a square in such a narrow space.\u00a0 Also not obvious in the discussion above is when the desired area is >= N*M-3.\u00a0 In this case the amount cut off a corner is 0 in some cases, which still works, it is just a bit unexpected considering all the use of diagonals in my description.<\/p>\n","protected":false},"excerpt":{"rendered":" Top 1000 advanced which looks to be solving question 1 completely and question 2 small in < 1:50.\u00a0 For safety add in the question 3 small input.\u00a0 In fact you could drop question 1 large.\u00a0 All 3 small inputs was sufficient to advance. Q1) Given a fraction, determine if it can be created by repeated … Continue reading GCJ14 R1C<\/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-755","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\/755","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=755"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/755\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=755"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=755"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=755"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} ## \n# #\n ##<\/pre>\n
##\n # #\n# #\n# #\n # #\n # #\n #<\/pre>\n
##\n# #\n# #\n #<\/pre>\n